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

The 20 questions

1. How is the capacity of a cut defined in a flow network?

   • Sum of capacities
   • Total net flow
   • Minimum arc capacity
   • Maximum arc capacity

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

   • The source S
   • The sink T
   • Only the source
   • All nodes

3. In network labelling, what does a forward arrow identify along an arc?

   • Spare capacity
   • Current flow
   • Residual deficit
   • Maximum capacity

4. In network labelling, what does a backward arrow identify along an arc?

   • Minimum flow
   • Reducible flow
   • Spare capacity
   • Total capacity

5. What name is given to a path from source to sink along which flow can be increased?

   • Augmenting path
   • Maximum route
   • Residual circuit
   • Critical path

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

   • Minimum cost
   • Maximum flow
   • Minimum cut
   • Shortest path

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 are backward arcs used during the network flow labelling procedure?

    • To create a loop
    • To block paths
    • To increase capacity
    • To cancel 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 an internal arc with both endpoints in set X not contribute to a cut capacity?

    • Connects to sink
    • Has zero capacity
    • Does not cross
    • Is directed backwards

19. What condition applies to an arc whose flow equals its capacity?

    • Saturated
    • Exhausted
    • Maximal
    • Optimal

20. What is the very first step when labelling a flow network?

    • Label source S
    • Find minimum cut
    • Label sink T
    • Saturate all arcs

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