Mathematics Standard • Year 12 • Module 5 • Lesson 10
Network Flow — Skill Drill
Build fluency in finding maximum flow by inspection and identifying minimum cuts. Verify with the max-flow min-cut theorem.
1. Quick recall
Answer each question in the space provided. 1 mark each
Q1.1 Complete the definitions. Source S: the vertex where ____________. Sink T: the vertex where ____________. Capacity of an edge: the ____________ that the edge can carry.
Q1.2 State the max-flow min-cut theorem in one short sentence: ____________________________.
Q1.3 A vertex V is between S and T (not S, not T). Flow conservation at V means ____________ = ____________.
2. Worked example — max flow and min cut
Follow every line. Each step has a reason on the right.
Problem. Pipes (capacities shown): S → A(10), S → B(5), A → T(8), B → T(6), A → B(3). Find max flow S → T and identify a minimum cut.
Step 1 — Push along S → A → T.
Bottleneck = min(S→A, A→T) = min(10, 8) = 8. Push 8. Remaining: S→A(2), A→T(0).
Step 2 — Push along S → B → T.
Bottleneck = min(5, 6) = 5. Push 5. Remaining: S→B(0), B→T(1).
Step 3 — Try S → A → B → T.
Bottleneck = min(S→A=2, A→B=3, B→T=1) = 1. Push 1.
Reason: routes through more than one intermediate vertex are valid; the bottleneck is the smallest remaining capacity along the path.
Step 4 — Total max flow.
Max flow = 8 + 5 + 1 = 14.
Step 5 — Find a cut with capacity 14 to confirm.
Cut {S, A, B} | {T}: edges leaving S-side toward T are A→T(8) and B→T(6). Sum = 14. ✓ Min cut = 14, matches max flow.
Conclusion. Maximum flow = 14. A minimum cut is {S, A, B} | {T}.
3. Faded example — fill in the missing steps
Pipes: S → A(4), S → B(3), A → B(2), A → T(5), B → T(4). Find max flow S → T and a min cut. 4 marks
Step 1 — Push S → A → T: bottleneck = min(____, ____) = ____. Push ____. Remaining: S→A = ____, A→T = ____.
Step 2 — Push S → B → T: bottleneck = min(____, ____) = ____. Push ____. Remaining: S→B = ____, B→T = ____.
Step 3 — Try S → A → B → T: remaining capacities = ____, ____, ____. Bottleneck = ____. Push ____.
Step 4 — Total max flow: ____ + ____ + ____ = ____.
Step 5 — Cut {S} | {A, B, T}: edges leaving S-side = S → A( ____ ) + S → B( ____ ) = ____.
Conclusion. Max flow = ____, minimum cut = ____. The two values are ____ (the same / different).
4. Graduated practice — max flow and min cut
Show paths and bottlenecks, then verify with a cut.
Foundation — single-step facts (4 questions)
| Q | Problem | Answer |
|---|---|---|
| 4.1 1 | True / False: max flow can exceed the capacity of some cut. | |
| 4.2 1 | Capacity of cut means sum of capacities of edges going from the ____-side to the ____-side. | |
| 4.3 1 | If every edge in a cut has capacity 4 and there are 3 such edges, the cut capacity is ____. | |
| 4.4 1 | A pipe with capacity 6 carries flow 4. Its remaining capacity is ____. |
Standard — typical HSC difficulty (6 questions)
Track flow on each pipe as you push, then check with a cut.
4.5 Pipes: S → A(6), S → B(4), A → C(3), B → C(5), C → T(7). Find max flow S → T. 2 marks
4.6 Pipes: S → A(5), S → B(2), A → T(4), B → T(3), A → B(1). Find max flow and identify a min cut. 2 marks
4.7 A network has max flow 9. A particular cut has capacity 10. Is this consistent? Justify in one sentence. 2 marks
4.8 A network has max flow 12. A particular cut has capacity 11. Is this consistent? Justify in one sentence. 2 marks
4.9 Pipes: S → A(8), A → T(5), A → B(4), B → T(7). Find max flow S → T. 2 marks
4.10 Explain in one sentence why flow conservation (inflow = outflow at every vertex except S and T) is required. 2 marks
Extension — combine ideas (2 questions)
4.11 Pipes: S → A(6), S → B(4), A → C(3), B → C(5), C → T(7), A → B(2), B → T(3). (a) Find max flow S → T. (b) Identify a minimum cut. (c) Verify the max-flow min-cut theorem. 3 marks
4.12 A network has S → A(5), S → B(5), A → T(3), B → T(3). The engineer upgrades S → A from 5 to 100. State the new max flow and explain in one sentence why the upgrade did not increase the throughput. 3 marks
5. Self-check the easy 3
Tick the first three once you've checked your method works.
How did this worksheet feel?
What I'll revisit before next class:
Q1.1 — Definitions
Source S: the vertex where all flow originates. Sink T: the vertex where all flow is collected. Capacity: the maximum amount of flow the edge can carry.
Q1.2 — Max-flow min-cut theorem
The maximum flow from S to T equals the capacity of the minimum cut.
Q1.3 — Flow conservation
At V, total inflow = total outflow.
Q3 — Faded example
Step 1: bottleneck = min(4, 5) = 4. Push 4. Remaining S→A = 0, A→T = 1.
Step 2: bottleneck = min(3, 4) = 3. Push 3. Remaining S→B = 0, B→T = 1.
Step 3: S → A → B → T: remaining caps = 0, 2, 1. Bottleneck = 0. Push 0.
Step 4: Total = 4 + 3 + 0 = 7.
Step 5: Cut {S} | {A, B, T}: S → A(4) + S → B(3) = 7.
Conclusion: max flow = 7 = min cut. The two values are the same.
Q4.1 — Can max flow exceed a cut?
False — by the max-flow min-cut theorem, flow ≤ capacity of every cut.
Q4.2 — Cut capacity direction
From the S-side to the T-side.
Q4.3 — Cut capacity
4 × 3 = 12.
Q4.4 — Remaining capacity
6 − 4 = 2.
Q4.5 — Max flow on 5-vertex network
S → A → C → T: min(6, 3, 7) = 3. S → B → C → T: min(4, 5, 7 − 3 = 4) = 4. Total = 7. Cut {S, A, B} | {C, T}: A→C(3) + B→C(5) = 8 (no edges from A or B directly to T). Cut {S, A, B, C} | {T}: C→T = 7. Min cut = 7. Max flow = 7.
Q4.6 — Max flow and min cut
S → A → T: min(5, 4) = 4. S → B → T: min(2, 3) = 2. S → A → B → T: min(5 − 4 = 1, 1, 3 − 2 = 1) = 1. Total = 4 + 2 + 1 = 7. Cut {S} | {A, B, T}: S→A(5) + S→B(2) = 7. ✓ Min cut = 7.
Q4.7 — Max flow 9, cut 10
Consistent — max flow (9) ≤ every cut capacity, so a cut of 10 is fine. (Min cut = 9 here.)
Q4.8 — Max flow 12, cut 11
Inconsistent — max flow can never exceed a cut capacity; max flow ≤ 11 in this case, contradicting "max flow = 12".
Q4.9 — Max flow with branch
S → A → T: min(8, 5) = 5. S → A → B → T: min(8 − 5 = 3, 4, 7) = 3. Total = 5 + 3 = 8. Cut {S} | {A, B, T}: S→A = 8. ✓
Q4.10 — Why flow conservation?
Without it, flow would either accumulate or disappear at intermediate vertices, which is physically and mathematically impossible — what enters a junction must leave it.
Q4.11 — Full max-flow problem (with A → B and B → T)
(a) Push S → A → C → T: min(6, 3, 7) = 3. Push S → B → C → T: min(4, 5, 7 − 3 = 4) = 4. Push S → B → T directly: but S → B already used 4 of 4, none left. Push S → A → B → T: min(6 − 3 = 3, 2, 3) = 2. Total = 3 + 4 + 2 = 9.
(b) Cut {S, A} | {B, C, T}: S→B(4) + A→C(3) + A→B(2) = 9.
(c) Max flow = 9 = capacity of min cut ✓ — max-flow min-cut theorem holds.
Q4.12 — Upgrade that doesn't help
Original max flow = min(5, 3) + min(5, 3) = 3 + 3 = 6. After upgrading S → A to 100: cut {S, A, B} | {T} has capacity A→T(3) + B→T(3) = 6. Max flow still 6. The upgrade did not help because the bottleneck is the cut after A and B (the A → T and B → T pipes), not the S → A pipe.