Exercises

1. For the graph shown in figure  find out the maximum flow. The weights given on edges are of maximum capacities of the edges.

   Figure: Flow graph.

   

2. List the minimum $s$-$t$ cuts in the flow network shown in figure .

   Figure: Flow graph.

   

3. What is minimum capacity of a $s$-$t$ cut in the flow network shown in figure .

   Figure: Flow graph.

   

4. For the graph shown in figure , answer the followings:
   1. Is this the maximum $s$-$t$ flow in this graph? Justify.
   2. Find the minimum $s$-$t$ cut in this flow network.

      Figure: Flow graph.

      

      Note: In $x/y$, $x$ is flow and $y$ is capacity. In case of single value, it is flow.

5. Re-write the Ford-Fulkerson algorithm in your words and explain its working.