Question: 3. Consider the following graph, which describes a flow network. 4(1) V. V6 5(3) 3(2) 2(2) V4 T2(1) 2(1) 1(1) (So V V Si 6(3)

3. Consider the following graph, which describes a flow network. 4(1) V. V6 5(3) 3(2) 2(2) V4 T2(1) 2(1) 1(1) (So V V Si 6(3) 3(1) V. 2(1) 2(2) 4(2) V3 Vs 3(2) Here, the vertex labeled So is the source, and the vertex labeled Si is the sink. The edge weightings indicate flow capacity, and the figures in brackets indicate the current flow through the network (i) Consider the following set of edges: C= {(S0,01), (03, Vs), (U5, 4-)}. a) Explain briefly why this set of edges forms a cut for the network. [4 marks] b) What is the capacity of this cut? [1 mark] c) Does there exist a cut for the network with a lower capacity than C? If so, find the cut with minimum capacity. If not, explain why such a lower capacity cut cannot exist
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
