4D.3.3 The max-flow min-cut theorem Quiz: Pearson Edexcel Further Maths, Unit 42

The 20 questions

1. What does the max-flow min-cut theorem state?

   • The minimum flow equals the maximum cut capacity.
   • The maximum flow from source to sink equals the minimum capacity of any cut.
   • The maximum flow is always the capacity of the largest cut.
   • The maximum flow equals the sum of all arc capacities.

2. How can the max-flow min-cut theorem be used to prove that a flow is maximum?

   • Show that the total cost of the flow is minimised.
   • Find a cut whose capacity equals the value of the flow.
   • Show that the flow is a whole number.
   • Show that every arc has flow equal to its capacity.

3. A flow of value 6 is found together with a cut of capacity 6. What follows?

   • The network has no augmenting path only if the cut is 11.
   • The flow is minimum and the cut is maximum.
   • The flow is maximum and the cut is minimum.
   • Both values must be checked against a third cut.

4. For a cut to show that a flow is maximal, what must be true of the forward arcs crossing the cut?

   • None of them may carry any flow.
   • They must all have flow equal to half their capacity.
   • Only the arcs leaving the sink must be full.
   • All of them must be full, with flow equal to capacity.

5. For a cut that proves a flow maximal, what must be true of the backward arcs crossing the cut?

   • They must carry flow equal to the forward arcs.
   • They must carry zero flow.
   • They must be saturated with flow equal to capacity.
   • They must have capacity zero.

6. Which statement is always true about any flow and any cut separating S from T?

   • The value of the flow is at least the capacity of the cut.
   • The flow value is always the capacity of the smallest arc.
   • The value of the flow is at most the capacity of the cut.
   • The value of the flow equals the capacity of every cut.

7. Why must a cut separate the source S from the sink T?

   • Otherwise flow could travel from S to T without crossing the cut, so the cut would not bound the flow.
   • Otherwise the cut capacity would always be zero.
   • Because cuts can contain only backward arcs.
   • So that the labelling procedure can start.

8. In a network with arcs S to A (4), S to B (3), A to B (2), A to T (2) and B to T (4), what is the capacity of the cut with X = {S, A, B}?

   • 8
   • 6
   • 7
   • 4

9. In the same network, what is the maximum flow from S to T?

   • 8
   • 6
   • 7
   • 5

10. In the same network, what is the capacity of the cut with X = {S}?

    • 6
    • 7
    • 5
    • 8

11. In the same network, what is the capacity of the cut with X = {S, B}?

    • 10
    • 8
    • 7
    • 6

12. A flow of value 5 is found in the same network. What can be concluded?

    • It is maximum, because some cut has capacity 5.
    • It is maximum, because 5 is less than every cut.
    • Nothing can be concluded, because cut capacity does not limit flow.
    • It is not maximum, because the minimum cut capacity is 6.

13. In the maximum flow S-A 4, S-B 2, A-B 2, A-T 2, B-T 4 of the network with arcs S to A (4), S to B (3), A to B (2), A to T (2), B to T (4), what is the net flow across the cut X = {S, A, B}?

    • 6
    • 4
    • 9
    • 3

14. In that maximum flow, which arc is not saturated?

    • S to A, which carries flow 4 against capacity 4.
    • B to T, which carries flow 4 against capacity 4.
    • A to T, which carries flow 2 against capacity 2.
    • S to B, which carries flow 2 against capacity 3.

15. When labelling in the same maximum flow, which vertices are labelled before the labelling stops?

    • S and A, but not B.
    • S and T.
    • S only.
    • S, A and B, but not T.

16. A flow of value 7 is claimed in a network that has a cut of capacity 6. Is this possible?

    • No, since every flow is at most the capacity of every cut.
    • Yes, if the flow is fractional.
    • Yes, if backward arcs are used.
    • Only if the cut is changed to X = {S}.

17. Why does saturating every forward arc of a cut and emptying every backward arc make the flow maximal?

    • No extra flow can cross the cut forwards, so the flow cannot grow beyond the cut capacity.
    • The cut then has zero capacity.
    • The flow must then be a whole number.
    • The labelling procedure cannot start.

18. In the network with arcs S to A (4), S to B (3), A to B (2), A to T (2) and B to T (4), the capacity of S to B is raised to 5. What is the new maximum flow?

    • 6
    • 9
    • 7
    • 8

19. In the network with arcs S to A (4), S to B (3), A to B (2), A to T (2) and B to T (4), the capacity of A to T is reduced to 1. What is the new maximum flow?

    • 6
    • 7
    • 4
    • 5

20. Two different maximum flows in the same network have the same value. Why?

    • Both equal the minimum cut capacity by the theorem, so their values must be equal.
    • All cuts have equal capacity.
    • Both use the same vertices.
    • Flows are unique in every network.

Related quizzes

• Cuts and augmenting flows by labelling Quiz · 4D.3.1-4D.3.2 · 20 questions
• Multiple sources, sinks and optimal flow rates Quiz · 4D.3.4-4D.3.5 · 20 questions
• Proof by mathematical induction Quiz · 1.1 · 20 questions
• Quadratic equations and complex arithmetic Quiz · 2.1-2.2 · 20 questions
• Matrix arithmetic and inverses Quiz · 3.1-3.2 · 20 questions
• Expectation of discrete random variables Quiz · 3B.1.1 · 20 questions
• The Poisson distribution Quiz · 3B.2.1 · 20 questions
• Geometric and negative binomial models Quiz · 3B.3.1 · 20 questions
• Hypothesis tests for the Poisson distribution Quiz · 3B.4.1 · 20 questions
• Applying the Central Limit Theorem Quiz · 3B.5.1 · 20 questions