Flows, cuts and the max-flow min-cut theorem Quiz

1. A network has arcs $SA$ 9, $SB$ 5, $AB$ 4, $BA$ 2, $AT$ 6 and $BT$ 8. Find the capacity of the cut $\{S,A\}|\{B,T\}$.

• A. $15$
• B. $17$
• C. $11$
• D. $34$

2. A flow of value 17 and a cut of capacity 17 are found in the same network. What can be concluded?

• A. The flow is not maximal
• B. The cut is not minimal
• C. The flow is maximal and the cut is minimal
• D. Nothing, because the network may have other flows

3. A problem has three factories and one warehouse. How is the supersource used?

• A. Arcs from each factory to the supersource
• B. Arcs from the supersource to each factory, with the factories' supply limits as capacities
• C. An arc from the supersource to the warehouse
• D. No change is needed

4. At an intermediate node, arcs carrying 6 and 5 enter and one arc carrying 7 leaves. What does the other outgoing arc carry?

• A. $18$
• B. $1$
• C. $7$
• D. $4$

5. The cuts of a network have capacities 13, 12 and 15. What is the greatest possible value of the maximum flow?

• A. $12$
• B. $13$
• C. $15$
• D. $40$