Question

graph below represents a network and the capacities are the sumber written on edges. The source is node a, and the target is node h. a. 10 (e) Show a fow of size 7 units going from the source a to the target h. (Write on the graph, next to the capacity, how many units of flow go through each edge.) (b) Consider the cut (L, R), wbere L (o) and R-(d.e.cf.s.Al, Indicate the edges crosig show that this cut has capacity equal to 9. (c) Joe claims that since the cut (L, R) from point (b) has capacity 9, the Max Flow Min Cut Theorem implies that there is a flow from a to h of size at least 9. Explain to Joe why he misunderstood the theorem (d) Show using the Max Flow Min Cut Theorem that there is no flow with size larger thas 7

Answer 1

a. Below is the image which shows non-zero flow passing through edge (a,b) , (b,c), (b,f) , (c,g) , (g,h), (a,e) , (e,f) , (f,h).

2/2 Cr 72 5/4 to/2 9 4/4- 8/5 h

b. Consider the same figure but with dotted line showing the cut. We can see that the cut with L = {a} and R = {b ,c,d,e,f,g,h} is passing through the edges (a,d) , (a, e) and (a,b) and the capacity of cut = sum of capacity of edges in cut = 3+5+1 = 9 unit

Cr b)-2/2 to/2 Cut 8/5

c. Although the cut (L,R) has capacity 9 unit, still it is not the min-cut because the flow from the edges in this cut are not completely saturated( i.e. there is still some edges whose capacity is not completely used) and hence max-flow will be less than or equal to 9 unit but it will never be greater than 9 unit.

d. Below image shows that Min-cut by dotted lines consists of complete saturated edges (b,c) , (b,f) , (e,f) with total flow = 2+1+4 = 7 unit. . Since all the edges in the cut shown below are completely saturated, so it is min-cut and by max-flow min-cut theorem, max-flow will always be equal to min-cut. Hence it is not possible to achieve flow more than 7 unit from a to h.

712 4 0/2 dl フ MIN-CUT

Please comment for any clarification.