Question

5 Network Flow, 90p. Consider the below flow network, with s the source and t the sink. 5 4 1. (10p) Draw a flow with value 8. (You may write it on top of the edges in the graph above, or draw a new graph.) You are not required to show how you construct the flow (though it may help you to apply say the Edmonds-Karp algorithm). 2. (5p) List a cut with capacity 8. (You may draw it in the original graph, or write whic nodes are with the source and which nodes are with the sink.) 3. (5p) Briefly explain why there cannot be a flow with value 9, or a cut with capacity

Answer 1

1. Below image shows the flow with capacity 8.

s/5 大 5/4 6/4

2. Below image shows the Min-cut by dotted line consists of completely saturated edge (A,C) , (D,C) , (D,t) of capacity 5+2+1 = 8 unit.

3 14 Mim-cut 3 4 6/4

3. Since the max-flow is equal to min-cut by max-flow min-cut theorem, hence we have just seen cut of size 8 unit in part b and hence flow value can not exceed more than size of any cut. Hence its not possible to achieve flow more than 8 unit.

Please comment for any clarification.