Exercises Exercises 415 maximum flow 1. (a) List all the minimum s-t cuts in the

Question

Exercises Exercises 415 maximum flow 1. (a) List all the minimum s-t cuts in the flow network pictured in Fig- ure 7.24. The capacity of each ed a label next to the edg What is the minimum capacity of an s-t cut in the flow network in Figure 7.25? Again, the capacity of each edge appears as a label next to the edge. (b) Figure 7.24 What are the minimum s-t cuts in this flow 2. network? Figure 7.26 shows a flow network on which an s-t flow has been computed. The capacity of each edge appears as a label next to the edge, and the numbers in boxes give the amount of flow sent on each edge. (Edges without boxed numbers-specifically, the four edges of capacity 3-have no flow being sent on them.) (a) what is the value of this flow? Is this a maximum (s,t) flow in this gran the flow network pictured in Figure 7.26, (b) Fir Figure 7.25 What is the min- imum capacity of an s-t cut in which an s t flow has been computed. this flow network? a label next to the edge, and the ow sent on each edge. (Edges 3. F TE

Explanation / Answer

Solution:

1)

a)

The minimum s-t cut is (s-u, u-t), and (s-v, v-t)

with the max flow of 2.

b)

The minimum capacity of the s-t cut is 2, here.

Because in all the augmenting path there is an edge with the capacity 2.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.