4D.3.1-4D.3.2 Cuts and augmenting flows by labelling Quiz: Pearson Edexcel Further Maths, Unit 42

The 20 questions

1. What is the capacity of a cut in a network with source S and sink T?

   • The sum of the capacities of the arcs directed from X to Y.
   • The sum of the capacities of the arcs directed from Y to X.
   • The smallest capacity of any single arc in the network.
   • The sum of the capacities of all arcs in the network.

2. In a cut separating source S from sink T, what must the set X contain?

   • At least the source S.
   • At least the sink T.
   • Every vertex except the source S.
   • Only the sink T.

3. In the labelling procedure, what does an arrow in the same direction as an arc identify?

   • The amount by which the flow along that arc can be increased.
   • The amount by which the flow along that arc can be decreased.
   • The capacity of the cut containing that arc.
   • The total flow through the source.

4. In the labelling procedure, what does an arrow in the opposite direction to an arc identify?

   • The lower capacity of the arc.
   • The amount by which the flow along that arc can be reduced.
   • The amount by which the flow along that arc can be increased.
   • The capacity of the arc in the forward direction.

5. What is an augmenting path?

   • A path from source to sink along which the flow can be increased.
   • A path that uses only backward arcs.
   • A path with the largest total capacity from source to sink.
   • A cycle returning to the source.

6. In a network with directed arcs only, what does the labelling procedure find?

   • The minimum cost route from source to sink.
   • The maximum flow from source to sink.
   • The optimal flow with lower bounds on each arc.
   • The shortest route in the network.

7. In the network with arcs S to A (5), A to B (2) and B to T (6), what is the most that can be sent along the path S-A-B-T at once from zero flow?

   • 13
   • 2
   • 6
   • 5

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

   • 11
   • 5
   • 9
   • 13

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

   • 11
   • 9
   • 6
   • 4

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

    • 15
    • 9
    • 11
    • 6

11. In the same network, what is the total flow leaving S if S to A carries 5 and S to B carries 4?

    • 4
    • 11
    • 5
    • 9

12. An arc S to A has capacity 5 and currently carries flow 2. By how much can the flow along that arc be increased?

    • 2
    • 5
    • 7
    • 3

13. Starting from zero flow in the network above, what is the largest amount that can be augmented along the path S-B-T?

    • 10
    • 6
    • 4
    • 2

14. After augmenting 2 along S-A-B-T and then 4 along S-B-T from zero flow, what is the total flow from S to T?

    • 6
    • 4
    • 2
    • 8

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

    • 11
    • 5
    • 9
    • 7

16. Why must backward arcs be considered in the labelling procedure?

    • Backward arcs define the cut capacity instead of forward arcs.
    • Backward arcs represent lower bounds only.
    • Backward arcs always have zero capacity and are ignored.
    • Flow already sent along an arc can be cancelled, which lets an augmenting path reroute flow.

17. An arc has capacity 10 and current flow 4. What is the forward residual capacity of this arc?

    • 10
    • 6
    • 4
    • 14

18. Why does the arc S to A not count towards the capacity of the cut with X = {S, A}?

    • Arcs leaving the source are never counted.
    • It points from Y to X, so it is ignored.
    • Both its endpoints lie in X, so it does not cross from X to Y.
    • Its flow is zero by definition.

19. What does it mean for an arc to be saturated?

    • Its flow equals its capacity, so it cannot be increased in the forward direction.
    • It has been removed from the network.
    • Its flow is zero, so it can take extra flow.
    • Its flow is greater than its capacity.

20. What is the first step when labelling a network from the source?

    • Label the source S, then label vertices reachable along arcs with spare capacity.
    • Label every arc with its capacity and stop.
    • Label the sink T first and work backwards only.
    • Label the vertices by their degree.

Related quizzes

• The max-flow min-cut theorem Quiz · 4D.3.3 · 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