DC1-DC3 Flows, cuts and the maximum flow-minimum cut theorem Quiz: AQA Further Maths, Unit 5

The 20 questions

1. In a flow network, what must equal outflow at any node except source and sink?

   • Cut value
   • Inflow
   • Capacity
   • Source flow

2. What term describes the maximum flow a directed arc can carry in a flow network?

   • Capacity
   • Excess flow
   • Cut
   • Saturated flow

3. Which arcs contribute to the capacity of a cut separating source S from sink T?

   • All crossing arcs
   • Forward arcs only
   • Backward arcs only
   • Undirected arcs only

4. What does the maximum flow in a network equal according to the max-flow min-cut theorem?

   • Total arc weight
   • Minimum cut capacity
   • Source node degree
   • Maximum cut capacity

5. 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). What is the maximum flow from S to T?

   • 5
   • 8
   • 6
   • 7

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). What is the capacity of the cut separating {S, A, B} from {T}?

   • 7
   • 8
   • 10
   • 5

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). What is the capacity of the cut separating {S, A} from {B, T}?

   • 6
   • 8
   • 11
   • 7

8. A network has source S and sink T with minimum cut capacity 7. What is its maximum flow?

   • 4
   • 14
   • 3
   • 7

9. In a valid network flow, what must equal the total flow into an intermediate node?

   • Node capacity limit
   • Source flow value
   • Total arc capacity
   • Total flow out

10. In a flow network, what is the value of the flow equal to?

    • Maximum arc capacity
    • Number of paths
    • Net source outflow
    • Total network capacity

11. At maximum flow, what state are all forward arcs of a minimum cut in?

    • Unused
    • Empty
    • Partially filled
    • Saturated

12. How do backward arcs affect the calculated capacity of a cut?

    • They subtract capacity
    • They add capacity
    • They add zero
    • They double capacity

13. A network has a feasible flow of 9 and cut capacity 10. What is the maximum flow lower bound?

    • 9
    • 19
    • 1
    • 10

14. A cut in a network has capacity 12. What does this capacity provide for maximum flow?

    • A lower bound
    • An upper bound
    • The minimum value
    • The exact value

15. 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). If the capacity of arc BT is reduced from 4 to 2, what is the new maximum flow from S to T?

    • 5
    • 3
    • 7
    • 6

16. 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 BT is reduced to capacity 2, which set of nodes gives a minimum cut, and what is its capacity?

    • {S, B} with capacity 6
    • {S, A, B} with capacity 5
    • {S} with capacity 7
    • {S, A} with capacity 8

17. If a network has a maximum flow of 12, what is its minimum cut capacity?

    • 6
    • 0
    • 12
    • 24

18. A directed network has source S and sink T. The arcs are SA (capacity 10), SB (capacity 5), AB (capacity 15), AT (capacity 5) and BT (capacity 10). What is the maximum flow from S to T?

    • 10
    • 20
    • 15
    • 25

19. What condition shows that the maximum flow in a network has been reached?

    • No backward arcs
    • All arcs saturated
    • No saturated arcs
    • No augmenting paths

20. What term describes a forward arc whose flow equals its capacity?

    • Reversed
    • Balanced
    • Saturated
    • Empty

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
• Supersources, augmenting flows and capacities Quiz · DC4-DC7 · 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