Chapter 7, Problem 1SE

To determine

The maximal flow and a minimal cut for given network by starting with the flow that is $0$ along every arc by flow augmentation algorithm.

Answer to Problem 1SE

The maximal flow and minimal cut for the given network is $\underset{\_}{\left\{A\right\}}$ and $\underset{\_}{\left\{B,C,D,E,F\right\}}$.

Explanation of Solution

Given:

The network is shown in Figure 1.

Concept used:

Flow Augmentation Algorithm

For a transportation network in which arc $\left(X,Y\right)$ has capacity $c\left(X,Y\right)$, this algorithm either indicates that the current flow $f$ is a maximal flow or else replaces $f$ with a flow having a larger value.

Step $1$ (Label the source)

Label the source with the triple $\left(source,+,\infty \right)$.

Step $2$ (Scan and label)

Step $2.1$ (select a vertex to scan)

Among all the vertices that have been labeled, but not scanned. Let $V$ denote the one that was labeled first, and suppose that the label on $V$ is $\left(U,\pm ,a\right)$.

Step $2.2$ (scan vertex $V$)

For each unlabeled vertex $W$, perform exactly one of the following three actions:

(a) If $\left(V,W\right)$ is an arc and $f\left(V,W\right)<c\left(V,W\right)$, assign to $W$ the label $\left(V,+,b\right)$, where $b$ is the smaller of $a$ and $c\left(V,W\right)-f\left(V,W\right)$.

(b) If $\left(W,V\right)$ is an arc and $f\left(W,V\right)>0$, assign to $W$ the label $\left(V,-,b\right)$ where $b$ is the smaller of $a$ and $f\left(W,V\right)$.

(c) If neither (a) and (b) holds, do not label W.

Step $2.3$ (mark as scanned)

Regard vertex $V$ as having been scanned.

Until either the sink is labeled or every labeled vertex has been scanned.

Step $3$ (increase the flow if possible)

If the sink is unlabeled the present flow is a maximal flow.

Otherwise

Step $3.1$ (breakthrough)

Let $V$ denote the sink and suppose that the label on $V$ is $\left(U,+,a\right)$.

Step $3.2$ (adjust the flow)

(a) If the label on $V$ is $\left(U,+,b\right)$ then replace $f\left(V,U\right)$ with $f\left(V,U\right)-a$.

(b) If the label on $V$ is $\left(U,-,b\right)$ then replace $f\left(V,U\right)$ with $f\left(V,U\right)-a$.

(c) Let $V$ denote the vertex $U$.

Until $V$ is the source.

Calculation:

The given network is shown in Figure $1$.

Label the given network as shown in Figure $2$.

Consider the path $A,B,D,F$ and label it as shown in Figure $3$.

Increase the flow by $5$ in the path $A,B,D,F$ and label the path $A,B,E,F$ as shown below in Figure $4$.

Increase the flow by $2$ in the path $A,B,E,F$ and label the path $A,C,D,E,F$ as shown below in Figure $5$.

Increase the flow by $4$ in the path $A,C,D,E,F$ and label the path $A,C,F$ as shown below in Figure $6$.

Increase the flow by $4$ in the path $A,C,F$ as shown below in Figure $7$.

The labeled vertices are $A$ and unlabeled vertices are $B,C,D,E,F$.

Label the sets as $\mathcal{S}=\left\{A\right\}$ and $\mathcal{T}=\left\{B,C,D,E,F\right\}$.

Therefore, the minimal cut for the given network is $\left\{A\right\}$ and $\left\{B,C,D,E,F\right\}$.

Thus, the above flow shown in Figure 7 has maximal flow and minimal cut for the given network is $\underset{\_}{\left\{A\right\}}$ and $\underset{\_}{\left\{B,C,D,E,F\right\}}$.