Unit 4 Topic 5 · CONFIRMED on Josh's school IA3 · teach in week 3, exam is week 4 · the 2019 QCAA sample has both (tank-fill flow, 3 marks CF; team-to-job assignment, 5.5 marks CF)
The concept in one sentence: a flow network moves stuff from a SOURCE to a SINK through pipes with capacities, and the tightest bottleneck (the minimum cut) sets the maximum flow; the Hungarian algorithm assigns n workers to n jobs at minimum total cost by pure procedure.
The thing that makes it click: for flow, "snip every path": a cut is a scissors line that severs EVERY route from source to sink, and the cheapest possible snip equals the maximum flow, exactly. For Hungarian: "make zeros, then chase them."
1 · Prerequisite check (30 seconds)
Can he follow a directed edge (arrow) and say which way the water goes? Can he subtract a number from a whole row of a table without slips?
Good news to say out loud: he already owns the core idea. The bottleneck question was in his drills weeks ago ("max flow is set by the tightest squeeze, not the biggest pipe"), and Hungarian is a procedure, which is his best format: no cleverness required, boring wins marks.
2 · The teaching path
Flow networks first:
Concrete: water pipes (or traffic, or a stadium's exits at full time). Source S = where it starts, sink T = where it ends, numbers on arrows = capacities, the most that pipe can carry. Direction matters: the arrows are one-way
Trace paths and saturate them: on the worked network below, push flow path by path (S-A-T carries 350, S-B-T carries 250...). He'll feel the limits appear
Cuts as scissors: draw dashed scissor-lines that sever EVERY path from S to T. Add up the capacity crossing each cut in the S-to-T direction. QCAA expects him to evaluate up to 8 cuts on one network, so make cut-hunting systematic: list them, total them, circle the smallest
The theorem, discovered: his best pushed flow and his cheapest cut come out EQUAL. That is minimum cut = maximum flow, and it works as a self-check from both ends
The exam garnish: flow questions often end in a rate calculation ("how long to fill a 4 500 L tank?"). Flow rate then time = volume ÷ rate. Two easy marks stapled to the network
maximum flow = minimum cut · a cut must sever EVERY source-to-sink path
Worked example (verified): S→A 400, S→B 300, A→B 100, A→T 350, B→T 250 (litres/min). Cuts: at the source 400 + 300 = 700; around {S, A}: 350 + 100 + 300 = 750; around {S, B}: 400 + 250 = 650; at the sink side {S, A, B}: 350 + 250 = 600 ← minimum. Max flow = 600 L/min, so a 4 500 L tank fills in 7.5 minutes.
Then Hungarian (pure procedure, teach it as a recipe card):
Row reduce: subtract each row's minimum from that row
Column reduce: subtract each column's minimum from that column
Cover test: cover all the zeros with as FEW straight lines as possible. Lines = n? Assign. Lines < n? Step 4
Adjust: find the smallest uncovered number, subtract it from every uncovered cell, add it at every line crossing. Back to step 3
Assign: pick zeros so each row and column gets exactly one. Read the answer from the ORIGINAL table
Worked example (verified): teams A, B, C quoting for jobs 1, 2, 3: A = 9, 11, 14 · B = 6, 15, 13 · C = 12, 13, 6. Row reduce → col reduce leaves zeros at A1, A2, B1, C3; three lines cover them, three assignments fall out: A→2, B→1, C→3, total 11 + 6 + 6 = $23 (matches the 2019 QCAA sample's structure exactly).
Does your line snip every path? If one path survives, it's not a cut.
Zeros first, then chase them.
One team, one job, read the cost off the original table.
3 · Misconception catalogue
Looks like
Why brains do it
The fix script
"Cut" that leaves a path alive
Snips SOME pipes and calls it done
"Trace S to T with your finger after cutting. If your finger arrives, the cut failed." Every cut gets the finger test
Adds every pipe in sight for max flow
More pipes = more flow feels right
Back to the drills line he already knows: "the tightest squeeze sets the flow, not the biggest pipe." Then find the squeeze
Counts a backwards edge in the cut total
The scissors crossed it, so it counts, right?
"Only capacity flowing FROM the source side TO the sink side counts. Water going backwards across your line doesn't help it forward." Arrow direction check on every crossed edge
Forgets flow in = flow out at middle nodes
Focuses on pipes, not junctions
"A junction can't store water. Whatever arrives must leave." Use it as the balance check on any completed flow
Hungarian: gives one team two jobs
Chases cheap zeros greedily
"One per row AND one per column, it's a seating plan, not a shopping spree"
Hungarian: reads the answer from the reduced table
The zeros live there, so the answer must too
"The reduced table finds WHO does WHAT. The MONEY lives in the original table." Two-step ritual: circle assignments, then flip back
Stalls when lines < n
The adjust step feels like a different algorithm
"Smallest uncovered number: subtract it everywhere uncovered, add it at the crossings, test again." Recipe card language, no why needed under exam pressure
4 · Questioning ladder
Rung
Ask
Listen for
Recall
"Max flow equals...?"
"Minimum cut", instantly
Do
The worked network above: find all four cuts, total each, name the max flow
600 via the {S, A, B} cut, with the finger test on each cut
Explain back
"Why must a cut sever every path?"
"If a path survives, water still gets through, so it doesn't cap the flow"
Transfer
"Same network. How long to fill a 4 500 L tank?"
4 500 ÷ 600 = 7.5 minutes, units said out loud
5 · How QCAA examines it
On Josh's IA3, confirmed. The 2019 sample shape: a flow network with a rate-and-volume tail (3 marks, CF) and a 3×3 Hungarian assignment with a "discuss the reasonableness of your assumption" tail (5.5 marks, CF)
Syllabus scope: flow networks with up to 8 cuts to evaluate; assignment problems 3×3 up to 5×5. Small, always solvable by the recipe
The reasonableness sentence: Hungarian questions often assume one team per job; the discussion mark = name the assumption and one consequence of relaxing it ("if team C could take two jobs, the answer might drop")
No formulas in the book for Topic 5, both methods are head-carried recipes, which is exactly why the recipe-card framing matters
Justify with the theorem: "the maximum flow is 600 L/min because the minimum cut is 600" is the full-marks sentence, cut named, theorem used
6 · Stuck scripts
Finger test: can you still get from S to T?
Which edge crossing your line actually points forward?
What's the next step on the recipe card?
Whose row has no circle yet?
7 · ADHD delivery notes
This is week 3 content with the exam in week 4: keep it to ONE sitting of each method plus drills, no depth-diving. Coverage now, polish never (the external revisits it in October anyway)
Hungarian's fixed recipe is genuinely his format: frame it as "the most boring algorithm in the course, and boring is unbreakable under pressure"
Cut-hunting in coloured pen (each candidate cut a different colour, totals in the margin) turns an abstract theorem into a colouring exercise
Both worked examples above are small on purpose (4 nodes, 3×3). The exam stays small too, say so, it lowers the dread