91Ó°ÊÓ

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.

(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}\})$ .

(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.

(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)$.

(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.

(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.