DC4-DC7 Supersources, augmenting flows and capacities Quiz: AQA Further Maths, Unit 5

The 20 questions

1. What is a supersource in a network with several sources?

   • A new node joined to every node, so that the network has one source of capacity equal to the total arc capacity
   • A node that replaces all the sources by one arc whose capacity equals the largest source capacity
   • A new node joined to every original source by arcs of very large capacity, so the network has a single source
   • A node that deletes all arcs leaving the original sources

2. What is a supersink in a network with several sinks?

   • A node that collects flow from the source and returns it to the start
   • A new node joined from the source by arcs of zero capacity
   • A new node joined from every original sink by arcs of very large capacity, so the network has a single sink
   • A node joined from every source, which removes flow from the network

3. What is an augmenting path in a flow network?

   • A cycle of arcs that all carry zero flow
   • A path from the sink back to the source that increases the total capacity
   • A path from source to sink that uses only arcs carrying their full capacity
   • A source-to-sink path along which flow can be increased, using forward arcs with spare capacity and backward arcs with positive flow

4. How is a node with a capacity limit represented in a flow network?

   • Delete all the arcs entering the node
   • Replace the node with an arc whose capacity equals the node's degree
   • Double the capacity of every arc entering the node
   • Split the node into an entry node and an exit node joined by an arc whose capacity equals the node capacity

5. What does a lower capacity on an arc in a flow network mean?

   • A minimum flow that must pass along the arc, in addition to its upper capacity limit
   • The capacity of the cut that the arc crosses
   • The minimum capacity of any arc in the network
   • The flow that the arc must not exceed when it leaves the sink

6. A directed network has source S and sink T, with arcs SA (capacity 4), SB (capacity 3), AB (capacity 2), AT (capacity 3) and BT (capacity 4). A flow of 3 currently passes along the route S-A-T only. How much can the flow be augmented along the route S-B-T?

   • 7
   • 3
   • 2
   • 4

7. A directed network has source S and sink T, with arcs SA (capacity 4), SB (capacity 3), AB (capacity 2), AT (capacity 3) and BT (capacity 4). A flow of 3 along S-A-T is augmented by 3 along S-B-T. What is the value of the resulting flow?

   • 6
   • 7
   • 9
   • 3

8. A directed network has source S and sink T, with arcs SA (capacity 4), SB (capacity 3), AB (capacity 2), AT (capacity 3) and BT (capacity 4). After the flow has value 6, what is the largest amount the flow can be augmented along the route S-A-B-T?

   • 2
   • 3
   • 4
   • 1

9. A directed network has source S and sink T, with arcs SA (capacity 4), SB (capacity 3), AB (capacity 2), AT (capacity 3) and BT (capacity 4). Which is the maximum flow value of this network, and what confirms it?

   • 9, confirmed by the arcs leaving S
   • 7, confirmed by the cut {S, A, B} with capacity 3 + 4 = 7
   • 6, confirmed by the cut {S} alone
   • 8, confirmed by the cut {S, A}

10. A network has two sources and one sink. Which construction correctly creates a single source?

    • Delete the original sources and connect the sink directly to every other node
    • Add a new node S with arcs from S to each original source, of very large capacity, and treat S as the source
    • Add a node S with arcs from each original source to S, each of capacity 1
    • Merge the original sources into one node whose capacity is zero

11. A network has one source and two sinks, T1 and T2. Which construction correctly creates a single sink?

    • Add a node T with arcs from the source to T1 and T2
    • Delete T1 and T2 and make the source the sink
    • Add a new node T with arcs from T1 and T2 to T of very large capacity, and treat T as the sink
    • Add a node T with arcs of zero capacity from T1 and T2

12. A node X has capacity 5, while its incoming arcs have total capacity 8. After X is split into X_in and X_out joined by an arc of capacity 5, what is the maximum flow through X?

    • 3
    • 5
    • 8
    • 13

13. An arc has lower capacity 2 and upper capacity 6. Which values of flow on this arc are allowed?

    • Any value from 2 to 6 inclusive
    • Any value from 2 to 4 inclusive
    • Any value from 0 to 2 inclusive
    • Any value from 4 to 8 inclusive

14. An arc has lower capacity 2 and upper capacity 6, and currently carries a flow of 4. Which statement is correct?

    • The flow can be increased by up to 6
    • The flow cannot change, since it lies strictly between the lower and upper capacities
    • The flow can be decreased by up to 4, but cannot be increased
    • The flow can be increased by up to 2 or decreased by up to 2

15. An augmenting path uses forward arcs with spare capacities 5 and 2 and 7, and a backward arc currently carrying flow 4. What is the largest amount by which the flow can be augmented along this path?

    • 7
    • 2
    • 4
    • 5

16. Why are the arcs joining a supersource to the original sources given very large capacities?

    • So that they become the minimum cut of the network
    • So that backward arcs can carry unlimited flow
    • So that all flow from the sources must be exactly equal
    • So that they never restrict the flow, and the maximum flow depends only on the original network

17. A node has capacity 6. Two incoming arcs each have capacity 4, and one outgoing arc has capacity 10. What is the maximum flow through the node?

    • 4
    • 8
    • 10
    • 6

18. In an augmenting-flow method, why can flow on a backward arc be reduced?

    • Because reducing flow on a backward arc creates new flow from the sink
    • Because reducing it reroutes flow, so the net flow through the network can still increase while conservation holds
    • Because backward arcs are not part of the network
    • Because backward arcs always have infinite capacity

19. A supersource S has arcs SS1 of capacity 5 and SS2 of capacity 7, and the sink can receive at most 9 units in total. What is the maximum flow from S to the sink?

    • 12
    • 7
    • 5
    • 9

20. Which statement about augmenting-flow methods is correct?

    • The method stops after one augmenting path, since the first path found is always maximal
    • The method stops only when no augmenting path exists, and at that point the flow value equals the minimum cut capacity
    • The method is valid only when all arcs have equal capacities
    • The method can only increase the flow on each arc and never decrease it

Related quizzes

• Graph language, Eulerian graphs and Euler's formula Quiz · DA1-DA3 · 20 questions
• Planarity, complete and bipartite graphs Quiz · DA4-DA5 · 20 questions
• Trees and isomorphism of graphs Quiz · DA6-DA7 · 20 questions
• Network language, spanning trees and route inspection Quiz · DB1-DB3 · 20 questions
• Travelling salesperson bounds and refining network models Quiz · DB4-DB5 · 20 questions
• Flows, cuts and the maximum flow-minimum cut theorem Quiz · DC1-DC3 · 20 questions
• Formulating and solving linear programmes graphically Quiz · DD1-DD2 · 20 questions
• The Simplex algorithm Quiz · DD3-DD4 · 20 questions
• Activity networks and critical paths Quiz · DE1-DE3 · 20 questions
• Refining models, Gantt charts and resource levelling Quiz · DE4-DE6 · 20 questions