Question

Consider the following network (the numbers are edge capacities).

(a)Find the maximum flow $\mathit{f}$and a minimum cut.

(b)Draw the residual graph${\mathit{G}}_{\mathbf{f}}$ (along with its edge capacities). In this residual network, mark the vertices reachable from$\mathbf{S}$ and the vertices from which$\mathit{T}$ is reachable.

(c)An edge of a network is called a bottleneck edge if increasing its capacity results in an increase in the maximum flow. List all bottleneck edges in the above network.

(d)Give a very simple example (containing at most four nodes) of a network which has no bottleneck edges.

(e)Give an efficient algorithm to identify all bottleneck edges in a network.

Short answer

(a)The maximum flow$f$ is$11$ , and a min-cut is $(\{S,A,B\},\{C,D,T\})$.

(b) The residual graph${\mathrm{G}}_{\mathrm{f}}$ is as follows,

The vertices reachable from$S$ are$A$ and $B$. The vertices reachable from$T$ are$C$ and$D$ .

(c)The bottleneck edges are$(\mathrm{A},\mathrm{C})$ and $(\mathrm{B},\mathrm{C})$.

(d)Simple example of a network that has no bottleneck edges is as follows:

(e) Algorithm to identify bottleneck edges in the network:

Procedure Bottleneck$({\mathrm{e}}_{\mathrm{n}},{\mathrm{e}}_{\mathrm{m}})$

Input: Graph $(V,E)$

Output: Bottleneck edges if exist

Perform max-flow min-cut in $G(V,E)$

Find Residual graph role="math" localid="1657972286397" ${\mathrm{G}}_{\mathrm{f}}$

Let$\mathrm{c}$ be the edge capacity of $G_f$

Ifrole="math" localid="1657972299309" $\mathrm{c}=0$ at ${\mathrm{e}}_{\mathrm{n}}$

If both ends have positive residual capacity

Mark as bottleneck edge

Return $({\mathrm{e}}_{\mathrm{n}},{\mathrm{e}}_{\mathrm{m}})$

Step-by-step solution

Explain Maximum flow and Min-cut

Consider the directed graph$\mathrm{G}=(\mathrm{V},\mathrm{E})$ with source$\mathrm{S}$ and sink $\mathrm{T}$.The maximum data must be sent from source to sink without exceeding the capacities of any other edges is the maximum flow. The maximum flow is denoted by role="math" localid="1657972699416" $\mathbf{f}$ . Min-cut is the partition of the vertices into two different groups and its capacity is the total capacity of the edges from the two disjoint groups.

Find maximum flow fand a minimum cut. 

(a)

Consider the network figure given in the question. The source is$S$ and the sink is$T$ in the graph $\mathrm{G}(\mathrm{V},\mathrm{E})$. The maximum flow does not violate the edge capacities; for all the nodes, the amount of flow entering the vertex must equal the amount leaving. The following Figure shows the Maximum flow and the minimum cut of the graph.

The flowing diagram illustrates the steps in finding the maximum flow.

Therefore, the maximum flow$f$ is$11$ , and a min-cut is$(\{\mathrm{S},\mathrm{A},\mathrm{B}\},\{\mathrm{C},\mathrm{D},\mathrm{T}\})$ .

Draw the residual graph and mark the vertices that reach from S and T . 

(b)

The residual graph captures the flow-increasing opportunities in the graph. The residual graph is represented by$G_f$ . The residual graph lists the two types of edges with residual capacities and flow.

The residual graph$G_f$ of the given network is as follows:

The vertices reachable from $S$are$A$ and$B$ . The vertices reachable from$T$ are$C$ and$D$ . The reachable vertices are represented as follows,

Therefore, the residual graph with the vertices reachable from source and sink is obtained.

Find the bottleneck edges.

(c)

If the maximum flow capacity increases with the edge’s capacity, then the edge is called the bottleneck edge. Here, maximum flow capacity increases at edges$(\mathrm{A},\mathrm{C})$and$(B,C)$ .

Hence, the bottleneck edges in the network are$(\mathrm{A},\mathrm{C})$ and $(B,C)$.

Example graph with no bottleneck edges.

(d)

The bottleneck edges increase the maximum flow of the network with an increase in their capacity.

The following is the example graph that has no bottleneck edges.

Thus, a network without bottleneck edges is obtained.

Algorithm to identify all the bottleneck edges. 

(e)

An efficient algorithm to identify all the bottleneck edges in-network is as follows:

Procedure Bottleneck$(e_n,e_m)$

Input: Graph $(V,E)$

Output: Bottleneck edges if exist

Perform max-flow min-cut in $G(V,E)$

Find Residual graph $G_f$

Let$C$ be the edge capacity of $G_f$

If $c=0$at $e_n$

If both ends have positive residual capacity

Mark as bottleneck edge

Return$(e_n,e_m)$

The algorithm calculates the graph’s maximum flow and the minimum cut. The residual graph is examined, and the capacity of the edges is checked. If the edge’s capacity is zero, then both the ends of the edges are checked for the positive residual capacity. The resultant edge is not a bottleneck edge.

Therefore, an algorithm to identify all the bottleneck edges is obtained.