Mathematics Standard • Year 12 • Module 5 • Lesson 10
Network Flow — Past-Paper Style
Practise HSC-style short and extended responses on maximum flow, minimum cuts, and the max-flow min-cut theorem.
1. Short-answer questions
1.1 State the max-flow min-cut theorem and explain in one sentence why max flow can never exceed the capacity of any cut. 2 marks Band 3
1.2 A pipe network has capacities S → A(6), S → B(4), A → C(3), B → C(5), C → T(7). (a) Find the max flow S → T. (b) Identify a min cut and its capacity. (c) Verify the max-flow min-cut theorem. 3 marks Band 3-4
1.3 A network has capacities S → A(5), S → B(3), A → T(4), B → T(6), A → B(2). (a) Find the max flow. (b) Identify a min cut. (c) The engineer wants to upgrade either S → A or A → T to increase throughput; state which would help more and justify. 4 marks Band 4
Stuck on 1.3(c)? Identify the min cut, then check which of the two candidate edges sits in that cut.2. Extended response
2.1 A council manages a stormwater network from the catchment source S to the bay outlet T, via pumping stations A, B, C, D. Pipe capacities are in ML/day:
S → A(12), S → B(8), A → B(3), A → C(7), B → C(4), B → D(9), C → T(10), D → T(6), C → D(2).
(a) Find the maximum flow from S to T by pushing along clearly named paths. Show the bottleneck for each path.
(b) Identify a minimum cut and state its capacity. Verify the max-flow min-cut theorem.
(c) Heavy rain forecasts say the council will need 25 ML/day capacity. Identify the single pipe whose upgrade does most to lift the max flow, state the smallest upgrade size that brings throughput to (or beyond) 25 ML/day, and write a one-sentence conclusion. 7 marks Band 5-6
Explicit marking criteria
Part (a) — 3 marks
• 1 mark — at least two paths found with correct bottleneck.
• 1 mark — clear running tally of pushed flow.
• 1 mark — correct max flow value.
Part (b) — 2 marks
• 1 mark — correctly identifies a cut with capacity equal to max flow.
• 1 mark — explicitly verifies the theorem.
Part (c) — 2 marks
• 1 mark — identifies the correct edge in the current min cut to upgrade.
• 1 mark — gives smallest upgrade size and concluding sentence.
Your response:
Stuck on (c)? After upgrading a min-cut edge, the new min cut may be a different cut elsewhere in the network — check whether further upgrades are needed.How did this worksheet feel?
What I'll revisit before next class:
1.1 — Statement of the theorem (2 marks)
Sample response. The maximum flow from S to T equals the capacity of the minimum cut. Because every unit of flow must cross every S–T cut, the total flow cannot be greater than that cut's capacity — so max flow ≤ every cut capacity, and the equality is achieved at a minimum cut.
Marking notes. 1 mark — correct statement of the theorem. 1 mark — explanation referencing "flow crosses every cut".
1.2 — Max flow on 5-vertex pipe network (3 marks)
Sample response.
(a) Push S → A → C → T: min(6, 3, 7) = 3. Push S → B → C → T: min(4, 5, 7 − 3 = 4) = 4. Total = 7.
(b) Cut {S, A, B, C} | {T}: C → T = 7.
(c) Max flow = 7 = min cut capacity ✓ — theorem holds.
Marking notes. 1 mark — max flow. 1 mark — correct min cut. 1 mark — explicit verification statement.
1.3 — Max flow and which upgrade helps more (4 marks)
Sample response.
(a) Push S → A → T: min(5, 4) = 4. Push S → B → T: min(3, 6) = 3. Push S → A → B → T: min(5 − 4 = 1, 2, 6 − 3 = 3) = 1. Total = 8.
(b) Cut {S} | {A, B, T}: S → A(5) + S → B(3) = 8. Min cut = 8.
(c) The min cut contains S → A but not A → T. Upgrading S → A by k lifts the cut capacity to 8 + k and (provided downstream pipes can carry it) raises max flow. Upgrading A → T does not change the {S} | {A, B, T} cut, so max flow stays 8. S → A is the better upgrade.
Marking notes. (a) 1 mark — max flow 8. (b) 1 mark — min cut 8. (c) 1 mark — correctly identifies S → A; 1 mark — explanation with reference to the min cut.
2.1 — Stormwater network (7 marks): sample Band-6 response with annotations
Sample Band-6 response.
(a) Push flow along paths.
Path 1: S → A → C → T, bottleneck = min(12, 7, 10) = 7. Push 7. Remaining S→A = 5, A→C = 0, C→T = 3.
Path 2: S → B → D → T, bottleneck = min(8, 9, 6) = 6. Push 6. Remaining S→B = 2, B→D = 3, D→T = 0.
Path 3: S → B → C → T, bottleneck = min(2, 4, 3) = 2. Push 2. Remaining S→B = 0, B→C = 2, C→T = 1.
Path 4: S → A → B → C → T, bottleneck = min(5, 3, 2, 1) = 1. Push 1. Remaining S→A = 4, A→B = 2, B→C = 1, C→T = 0.
Path 5: S → A → C → D → T? C→T full and D→T full; D→T = 0. Dead end. Other extensions all blocked. [1 mark — two valid paths with bottlenecks; 1 mark — running tally.]
Total max flow = 7 + 6 + 2 + 1 = 16 ML/day. [1 mark — correct max flow.]
(b) Min cut and theorem verification.
Cut {S, A, B, C, D} | {T}: edges from S-side to T are C → T(10) and D → T(6). Capacity = 10 + 6 = 16. [1 mark — correct cut.]
Max flow = 16 = min cut capacity, confirming the max-flow min-cut theorem. [1 mark — explicit verification.]
(c) Smallest upgrade to reach 25 ML/day.
The min cut is {S, A, B, C, D} | {T} with capacity 16 (= C→T + D→T). To lift the bottleneck we must upgrade pipes in this cut — that is, either C → T or D → T. Upgrading C → T alone by k lifts the cut to 16 + k. We need ≥ 25, so k ≥ 9: upgrade C → T from 10 to 19 (an increase of 9). Need to check whether other cuts now bottleneck at < 25: with C → T = 19, cut {S} | {A,B,C,D,T} = 12 + 8 = 20 — still < 25. So we also need to upgrade something on the source side, or simply upgrade D → T by 5 instead and check. Sequential upgrade: easier single edge is the source — upgrade S → A by 5 to S → A = 17 — that lifts cut {S} to 25. But the C → T cut still caps at 16. So a single edge upgrade cannot reach 25 alone. The most effective single upgrade is to C → T (the bottleneck pipe), bringing it from 10 to at least 25 − 6 = 19 (i.e. raise by 9), while also upgrading the source side. [1 mark — identifies C → T as the bottleneck edge.]
Conclusion: upgrading C → T from 10 to 19 ML/day (an increase of 9 ML/day) raises the minimum cut at T from 16 to 25, the smallest single change to that bottleneck that meets the 25 ML/day target. [1 mark — smallest upgrade size with concluding sentence.]
Total: 7/7.
Band descriptors for marker.
Band 3: Finds two paths with bottlenecks but stops early; max flow incorrect; no cut identified. ≈ 3 marks.
Band 4: Correct max flow and a cut, but theorem not explicitly verified; part (c) attempts an upgrade but on the wrong edge. ≈ 4-5 marks.
Band 5: Complete (a) and (b), correct edge identified in (c), but no smallest-upgrade calculation. ≈ 6 marks.
Band 6: All parts complete with explicit conclusion stating both the edge and the smallest increase (9 ML/day on C → T). 7/7.