3. Max-flow and Min-cut. (20 points) You are given the following flow graph G = (V, E, s, t) with the indicated edge capacities. 9 V1 U2 12 20 3 9 6 s 5 15 2 11 7 14 V3 V4 a.) (15 points) Use the Ford-Fulkerson algorithm to find the maximum flow for graph G. In every iteration, show the residual network, the augmented path you chose, and the updated flows. b.) (5 points) Determine the cut (by specifying the edges in the cut) with capacity equal to the maximum flow you found in part (a). Explain why this is the minimum cut. 4. Multi-Source Max-Flow. (10 points) Consider a variant of the max-flow problem where, instead of having just a single sources, the input graph G = (V, E) now has k sources $1,S2, ..., 88. Thus, the value of the flow is redefined to be the sum of the flows leaving all sources (SI = Di- vev f($,v). Explain how you can transform graph G into another graph G' that has a single source and show how a max-flow solution to G' can be translated into a max-flow solution to the multi-source G. (Hint: recall that we did something similar for the bipartite matching problem). 3 3. Max-flow and Min-cut. (20 points) You are given the following flow graph G = (V, E, s, t) with the indicated edge capacities. 9 V1 U2 12 20 3 9 6 s 5 15 2 11 7 14 V3 V4 a.) (15 points) Use the Ford-Fulkerson algorithm to find the maximum flow for graph G. In every iteration, show the residual network, the augmented path you chose, and the updated flows. b.) (5 points) Determine the cut (by specifying the edges in the cut) with capacity equal to the maximum flow you found in part (a). Explain why this is the minimum cut. 4. Multi-Source Max-Flow. (10 points) Consider a variant of the max-flow problem where, instead of having just a single sources, the input graph G = (V, E) now has k sources $1,S2, ..., 88. Thus, the value of the flow is redefined to be the sum of the flows leaving all sources (SI = Di- vev f($,v). Explain how you can transform graph G into another graph G' that has a single source and show how a max-flow solution to G' can be translated into a max-flow solution to the multi-source G. (Hint: recall that we did something similar for the bipartite matching problem). 3