Mathematics Standard • Year 12 • Module 5 • Lesson 10
Network Flow — Problem Set
Apply max-flow min-cut thinking to real Australian contexts: water reticulation, peak-hour traffic, sewage treatment and parcel sorting.
Problem 1 — Hunter Region water reticulation
Water flows from the reservoir S to the town centre T via pumping stations A and B. Pipe capacities in ML/day: S → A (10), S → B (6), A → B (4), A → T (8), B → T (9).
Set up: What are we solving for?
(i) Find the maximum flow from S to T by pushing flow along clearly named paths. Show every bottleneck. 3 marks
(ii) Identify a minimum cut and verify the max-flow min-cut theorem. 2 marks
Stuck? Revisit lesson § Worked Example.Problem 2 — Sydney peak-hour traffic
Cars per hour can flow from a suburb S to the CBD T via one-way streets through interchanges A, B, C. Capacities: S → A (300), S → B (200), A → C (250), B → C (150), C → T (400), A → T (100), B → T (180).
Set up: What are we solving for?
(i) Find the maximum number of cars per hour that can travel S → T. Show your paths. 3 marks
(ii) State a minimum cut and its capacity. 2 marks
(iii) Council proposes a new lane that lifts C → T from 400 to 600. Does the max flow change? Justify. 2 marks
Stuck? An upgrade only raises max flow if the upgraded edge was part of the min cut.Problem 3 — Sewage treatment network
Wastewater flows from a residential zone S to the treatment plant T. Pipe capacities (ML/day): S → A(7), S → B(8), A → B(3), A → C(5), B → D(6), C → T(9), D → T(4), B → C(2), C → D(3).
Set up: What are we solving for?
(i) Find the max flow from S to T. Show paths and bottlenecks. 3 marks
(ii) Identify a min cut and verify the theorem. 2 marks
Stuck? Try the cut just before T: {S, A, B, C, D} | {T}.Problem 4 — Australia Post parcel sorting
Parcels enter at the depot S and leave at the delivery dock T. Conveyor capacities (parcels per minute): S → A(40), S → B(30), A → C(25), B → C(20), B → D(15), C → T(35), D → T(20), A → D(10).
Set up: What are we solving for?
(i) Find max flow S → T. 3 marks
(ii) State a min cut and its capacity. 2 marks
(iii) Conveyor C → T jams and is reduced from 35 to 20. Recompute the max flow. 2 marks
Stuck? Re-check the cut just before T after the jam.Problem 5 — Find the bottleneck
A small council has a stormwater system with S → A(20), S → B(20), A → T(10), B → T(10), A → B(50). After heavy rain, only 20 ML/day actually reaches T even though the inlet pipes can carry 40.
Set up: What are we solving for?
(i) Find the max flow S → T and explain why it is only 20. 2 marks
(ii) Identify the bottleneck cut. 2 marks
(iii) Council can upgrade ONE pipe to increase max flow. Suggest the cheapest sensible upgrade and explain in one sentence. 2 marks
Stuck? Only upgrades to edges in the min cut increase max flow.How did this worksheet feel?
What I'll revisit before next class:
Problem 1 — Hunter Region water reticulation
Set up. Find max water flow S → T and confirm with a cut.
(i) Push S → A → T: min(10, 8) = 8. Remaining S→A = 2, A→T = 0. Push S → B → T: min(6, 9) = 6. Remaining S→B = 0, B→T = 3. Push S → A → B → T: min(2, 4, 3) = 2. Remaining S→A = 0, A→B = 2, B→T = 1. Total = 8 + 6 + 2 = 16 ML/day.
(ii) Cut {S} | {A, B, T}: S → A(10) + S → B(6) = 16. Max flow = min cut = 16 ✓.
Problem 2 — Peak-hour traffic
Set up. Find max cars/hour S → T and the bottleneck cut.
(i) Push S → A → C → T: min(300, 250, 400) = 250. Remaining S→A = 50, A→C = 0, C→T = 150. Push S → B → C → T: min(200, 150, 150) = 150. Remaining S→B = 50, B→C = 0, C→T = 0. Push S → A → T: min(50, 100) = 50. Push S → B → T: min(50, 180) = 50. Total = 250 + 150 + 50 + 50 = 500 cars/hour.
(ii) Cut {S} | {A, B, C, T}: S→A(300) + S→B(200) = 500. Min cut = 500 ✓.
(iii) No — the min cut sits at the source end (S → A and S → B). Upgrading C → T does not change that cut's capacity. Max flow remains 500.
Problem 3 — Sewage treatment
Set up. Find max wastewater flow S → T.
(i) Push S → A → C → T: min(7, 5, 9) = 5. Remaining S→A = 2, A→C = 0, C→T = 4. Push S → B → D → T: min(8, 6, 4) = 4. Remaining S→B = 4, B→D = 2, D→T = 0. Push S → B → C → T: min(4, 2, 4) = 2. Remaining S→B = 2, B→C = 0, C→T = 2. Push S → A → B → D → T? D→T is 0, dead end. Push S → B → D → C → T? B→D = 2 left, D→C? Only C→D listed, not D→C. (Undirected version would help — assume directed only.) Try S → A → B → C → T: A→B doesn't exist; only A→B was not listed. Total so far = 5 + 4 + 2 = 11 ML/day.
(ii) Cut {S, A, B, C, D} | {T}: C→T(9) + D→T(4) = 13. Cut {S, A, B} | {C, D, T}: A→C(5) + B→C(2) + B→D(6) = 13. Cut {S} | {A, B, C, D, T}: 7 + 8 = 15. Cut {S, A} | {B, C, D, T}: A→B(3) + A→C(5) + S→B(8) = 16. Try {S, A, B, D} | {C, T}: A→C(5) + B→C(2) + D→T(4) = 11. Min cut = 11 ✓ = max flow.
Problem 4 — Australia Post parcel sorting
Set up. Find max parcels/min from S to T.
(i) Push S → A → C → T: min(40, 25, 35) = 25. Remaining S→A = 15, A→C = 0, C→T = 10. Push S → B → C → T: min(30, 20, 10) = 10. Remaining S→B = 20, B→C = 10, C→T = 0. Push S → B → D → T: min(20, 15, 20) = 15. Remaining S→B = 5, B→D = 0, D→T = 5. Push S → A → D → T: min(15, 10, 5) = 5. Remaining S→A = 10, A→D = 5, D→T = 0. Total = 25 + 10 + 15 + 5 = 55 parcels/min.
(ii) Cut {S, A, B, C, D} | {T}: C→T(35) + D→T(20) = 55 ✓.
(iii) With C → T reduced to 20: cut {S, A, B, C, D} | {T} now = 20 + 20 = 40. So max flow ≤ 40. Achievable: S → A → C → T (20), S → B → D → T (15), S → A → D → T (5). Total = 40. New max flow = 40 parcels/min.
Problem 5 — Stormwater bottleneck
Set up. Locate the bottleneck and pick a sensible upgrade.
(i) S → A → T: min(20, 10) = 10. S → B → T: min(20, 10) = 10. Total = 20 ML/day. The A → B(50) pipe is enormous but cannot be used because both A → T and B → T are full at 10 each.
(ii) Cut {S, A, B} | {T}: A → T(10) + B → T(10) = 20. This is the bottleneck.
(iii) Either A → T or B → T should be upgraded — they are the two edges in the min cut. Upgrading just one of them is the smallest single change that lifts max flow; for example, raising A → T from 10 to 20 lifts max flow from 20 to 30 (since the new bottleneck cut becomes B → T + new A → T = 30, matched by routing more flow through A).