Network flow

5. (a) Given a network G and distinct nodes s,t in G. ) Define what an s, t-cut is, and what the capacity of a cut is. (ii) State the minimum cut problem. 2 marks] (b) Copy the following network G into your answering book. (i) Indicate a maximum flow f and draw the residual graph Gy for this flow (i) Indicate a mimimum s, t cut. What is the capacity of your cut? i) Why does this show the flow is maximal? Note: you are not required to run the Ford-Fulkerson algorithm.) 3 marks] 110 102 170 (c) Briefly explain why the running time of the original Ford Fulkerson algorithm is not polyno- [1 mark] (d) Briefly explain which kind of improvement makes the running time polynomial.[ mark] I mark] (f) Indicate how this maximum bipartite matching problem can be reduced to the problem of 2 marks mial on a general input (e) Describe the maximum matching problem in a bipartite graph. finding a maximum flow in a network 5. (a) Given a network G and distinct nodes s,t in G. ) Define what an s, t-cut is, and what the capacity of a cut is. (ii) State the minimum cut problem. 2 marks] (b) Copy the following network G into your answering book. (i) Indicate a maximum flow f and draw the residual graph Gy for this flow (i) Indicate a mimimum s, t cut. What is the capacity of your cut? i) Why does this show the flow is maximal? Note: you are not required to run the Ford-Fulkerson algorithm.) 3 marks] 110 102 170 (c) Briefly explain why the running time of the original Ford Fulkerson algorithm is not polyno- [1 mark] (d) Briefly explain which kind of improvement makes the running time polynomial.[ mark] I mark] (f) Indicate how this maximum bipartite matching problem can be reduced to the problem of 2 marks mial on a general input (e) Describe the maximum matching problem in a bipartite graph. finding a maximum flow in a network