4D.3.4-4D.3.5 Multiple sources, sinks and optimal flow rates Quiz: Pearson Edexcel Further Maths, Unit 42

The 20 questions

1. How is a network with several sources converted to one with a single source?

   • Add a supersource S joined to each original source, with capacities as described.
   • Merge all the sources into one vertex and delete their arcs.
   • Replace each source with a sink.
   • Remove the sources and treat their arcs as backward arcs.

2. What is the capacity of the arc from the supersource to a source S1?

   • The largest capacity of any arc leaving S1.
   • The sum of the capacities of the arcs leaving S1.
   • Infinite, always.
   • The capacity of the cheapest arc leaving S1.

3. How is a network with several sinks converted to one with a single sink?

   • Delete the sinks and add their arcs to the source.
   • Give each sink a demand of zero and remove its arcs.
   • Connect each sink to a supersink T, with the arc capacity equal to the capacity of the arcs entering that sink.
   • Connect each sink to a source with zero capacity.

4. What is the capacity of the arc from a sink T1 to the supersink T?

   • The sum of the capacities of the arcs leaving T1.
   • The largest capacity of the arcs entering T1.
   • Zero, since T1 is a sink.
   • The sum of the capacities of the arcs entering T1.

5. How is a vertex with restricted capacity modelled in a flow network?

   • Double every arc connected to it.
   • Delete the vertex and add its capacity to every incoming arc.
   • Replace it with an arc of infinite capacity.
   • Replace it by two vertices joined by an arc with the restricted capacity.

6. What is a lower capacity on an arc in a flow network?

   • The minimum flow that must pass along that arc.
   • The cost of sending one unit along the arc.
   • The maximum flow allowed along the arc.
   • The flow that is never allowed on the arc.

7. With upper and lower capacities, how is the capacity of a cut calculated?

   • Sum the upper capacities of arcs crossing from S-side to T-side, then subtract the lower capacities of arcs crossing from T-side to S-side.
   • Sum all the upper capacities that cross the cut.
   • Sum the lower capacities of arcs crossing from S-side to T-side.
   • Sum the upper capacities and subtract all the lower capacities in the network.

8. In the network with source S1 joined to A (4) and B (3), source S2 joined to B (5), A to T (6) and B to T (4), what is the capacity of the supersource arc to S1?

   • 4
   • 12
   • 5
   • 7

9. In the same network, what is the maximum flow from the sources to the sink?

   • 10
   • 8
   • 7
   • 12

10. In the same network, what is the capacity of the cut X = {SS, S1, S2, B}?

    • 10
    • 14
    • 12
    • 8

11. Which set X gives the minimum cut in the same network?

    • {SS, S1, S2, A}
    • {SS, S1, S2, A, B}
    • {SS, S1, S2}
    • {SS, S1, S2, B}

12. A supersink T is joined from T1 by arcs of capacity 3 and 2 entering T1. What is the capacity of the arc from T1 to T?

    • 2
    • 6
    • 3
    • 5

13. A vertex B has capacity 4. What is the capacity of the arc joining its two new vertices after splitting?

    • 2
    • 6
    • 4
    • 8

14. An arc from S-side to T-side has upper capacity 8 and lower capacity 2. An arc from T-side to S-side has upper capacity 5 and lower capacity 1. What is the capacity of the cut?

    • 8
    • 13
    • 7
    • 9

15. An arc has upper capacity 10 and lower capacity 4. Between what values can the flow along this arc lie?

    • From 4 to 10 inclusive.
    • From 0 to 4 inclusive.
    • From 0 to 10 inclusive.
    • From 4 to 6 inclusive.

16. Why does the supersource construction leave the maximum flow unchanged?

    • The new arcs have infinite capacity, which is ignored.
    • The supersource has zero capacity.
    • The new sink has zero demand.
    • The new arcs carry exactly what the original sources could supply, so no extra flow is created.

17. In the network with sources S1 and S2 and sink T, the capacity of B to T is reduced to 2. What is the new maximum flow?

    • 10
    • 8
    • 6
    • 4

18. What is the total capacity of the arcs leaving the supersource in the same network?

    • 7
    • 8
    • 10
    • 12

19. Why can the lower-capacity cut formula not simply use upper capacities?

    • Lower capacities always exceed upper capacities, so they are removed.
    • The cut ignores arcs that have a lower capacity.
    • Lower capacities add to the cut only when they cross from S-side to T-side.
    • An arc from T-side to S-side with a lower bound forces flow backwards across the cut, which reduces the net flow that can go forwards.

20. Why does splitting a vertex with restricted capacity keep the flow through the vertex within its limit?

    • Each split vertex gets infinite capacity, so the limit is lost.
    • All flow through the vertex must cross the joining arc, which has the restricted capacity.
    • The split doubles the flow, which is then halved.
    • The joining arc has zero cost, so flow is unrestricted.

Related quizzes

• Cuts and augmenting flows by labelling Quiz · 4D.3.1-4D.3.2 · 20 questions
• The max-flow min-cut theorem Quiz · 4D.3.3 · 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