Mathematics Standard • Year 12 • Module 5 • Lesson 12
Module Review — Problem Set
Apply the full module 5 toolkit to five Australian planning scenarios — each requires identifying the right concept and then using the matching algorithm.
Problem 1 — Sydney Marathon event network
Six aid stations P, Q, R, S, T, U are along the marathon route. Roads between them (in km): PQ = 4, PR = 6, QR = 3, QS = 8, RS = 5, RT = 7, ST = 2, SU = 9, TU = 4.
Set up: Three different organising questions.
(i) Council wants to upgrade the cheapest set of roads so every aid station is reachable. Find the MST and total. 2 marks
(ii) An ambulance needs the shortest route from P (start) to U (finish). Find distance and route. 2 marks
(iii) A volunteer wants to walk every road exactly once. Show whether this is possible (Eulerian trail / circuit / neither). 2 marks
Stuck? List the degrees of P, Q, R, S, T, U before deciding.Problem 2 — Riverina water grid
A water utility has a pipeline from reservoir S to town T via pumping stations A, B, C. Pipe capacities (ML/day): S → A(8), S → B(5), A → B(3), A → C(4), B → C(2), B → T(6), C → T(7).
Set up: Max flow and min cut.
(i) Find the max flow S → T. Show paths and bottlenecks. 3 marks
(ii) Identify a min cut and verify the max-flow min-cut theorem. 2 marks
(iii) If pipe A → C is upgraded from 4 to 10 ML/day, does max flow increase? Justify in one sentence. 2 marks
Stuck? Check whether A → C is in the current min cut.Problem 3 — Regional NSW road agency
The agency plans roads between five towns A, B, C, D, E with costs in $millions: AB = 4, AC = 2, AD = 6, BC = 3, BD = 5, BE = 7, CD = 1, CE = 4, DE = 3.
Set up: Several questions on one network.
(i) Find the MST using Kruskal's algorithm. State edges and total. 2 marks
(ii) Find shortest A → E using Dijkstra's. State distance and route. 2 marks
(iii) A courier needs to visit every town exactly once, starting and ending at A. Find a Hamiltonian cycle or explain why none exists. 2 marks
Stuck on (iii)? Try A → C → D → E → B → A and check every edge exists.Problem 4 — Local postie's round
A suburb is modelled as a network on vertices A, B, C, D, E. Edges (streets) are AB, AC, BC, BD, CD, CE, DE. The postie wants to walk every street exactly once and return to the post office at A.
Set up: Eulerian check, then suggest a fix.
(i) List the degree of each vertex. 1 mark
(ii) Is an Eulerian circuit (start = end = A) possible? Justify with the degree condition. 2 marks
(iii) If not a circuit, is at least an Eulerian trail possible? Where could it start and end? 2 marks
(iv) Suggest the smallest change to the network (add or remove one street) so an Eulerian circuit becomes possible. 2 marks
Stuck? Adding or removing one edge changes the parity of two vertices' degrees.Problem 5 — Choose and solve
For each scenario, identify the algorithm in one phrase and then solve the small problem given.
Set up: Rapid identify-then-apply drill.
(i) "Cheapest way to wire a 4-house cul-de-sac, edges HA = 3, HB = 4, HC = 5, AB = 2, BC = 6, AC = 7 (H = hub)." Algorithm + MST total. 2 marks
(ii) "Fastest A → C with edges AB = 3, AC = 7, BC = 2." Algorithm + shortest A → C. 2 marks
(iii) "Max flow with S → A(5), S → B(2), A → T(4), B → T(3)." Algorithm + max flow. 2 marks
Stuck? Three small networks, three different algorithms.How did this worksheet feel?
What I'll revisit before next class:
Problem 1 — Sydney Marathon event network
Set up. MST, shortest path, Eulerian check.
(i) Kruskal's. Sort: ST(2), QR(3), PQ(4), TU(4), RS(5), PR(6), RT(7), QS(8), SU(9). Add ST, QR, PQ, TU (→ {P,Q,R,S,T,U} after RS pulls in S? Wait, after ST, QR, PQ: {S,T} and {P,Q,R}. Add TU(4): {S,T,U}, {P,Q,R}. Add RS(5): joins them → {P,Q,R,S,T,U}. Stop (5 edges). MST = ST, QR, PQ, TU, RS. Total = 2 + 3 + 4 + 4 + 5 = $18 m (or 18 km).
(ii) Dijkstra from P. P = 0. Visit P: Q = 4, R = 6. Visit Q (4): R = min(6, 7) = 6, S = 12. Visit R (6): S = min(12, 11) = 11, T = 13. Visit S (11): T = min(13, 13) = 13, U = 20. Visit T (13): U = min(20, 17) = 17. Visit U (17). Shortest P → U = 17 km; path P → R → T → U (6 + 7 + 4 = 17) or P → Q → R → T → U (4 + 3 + 7 + 4 = 18 longer).
(iii) Degrees: P (PQ, PR) = 2. Q (PQ, QR, QS) = 3. R (PR, QR, RS, RT) = 4. S (QS, RS, ST, SU) = 4. T (RT, ST, TU) = 3. U (SU, TU) = 2. Odd vertices: Q and T (exactly 2). Eulerian trail exists (start at Q or T, end at the other). No Eulerian circuit.
Problem 2 — Riverina water grid
Set up. Max flow and min cut.
(i) Path S → A → C → T: min(8, 4, 7) = 4. Remaining S→A = 4, A→C = 0, C→T = 3. Path S → B → T: min(5, 6) = 5. Remaining S→B = 0, B→T = 1. Path S → A → B → C → T: min(4, 3, 2, 3) = 2. Remaining S→A = 2, A→B = 1, B→C = 0, C→T = 1. Path S → A → B → T: min(2, 1, 1) = 1. Remaining S→A = 1, A→B = 0, B→T = 0. Total = 4 + 5 + 2 + 1 = 12 ML/day.
(ii) Cut {S, A, B, C} | {T}: B→T(6) + C→T(7) = 13. Cut {S, A} | {B, C, T}: S→B(5) + A→B(3) + A→C(4) = 12. Min cut = 12 ✓ = max flow.
(iii) No — A → C is not the bottleneck. The min cut {S, A} | {B, C, T} contains A → C (4), but increasing only A → C while leaving S → B (5) and A → B (3) fixed leaves the cut at 5 + 3 + 10 = 18, but other cuts (e.g. {S, A, B, C} | {T} = 13) now bind. Re-run to confirm: max flow with A→C = 10 is still 12, because the bottleneck moves to the C→T / B→T cut. Max flow stays 12.
Problem 3 — Regional NSW roads
Set up. MST, shortest path, Hamiltonian cycle.
(i) Kruskal's. Sort: CD(1), AC(2), BC(3), DE(3), AB(4), CE(4), BD(5), AD(6), BE(7). Add CD, AC, BC (→ {A,B,C,D}), DE (→ {A,B,C,D,E}). Stop (4 edges). MST = CD, AC, BC, DE; total = 1 + 2 + 3 + 3 = $9 million.
(ii) Dijkstra from A. A = 0. Visit A: B = 4, C = 2, D = 6. Visit C (2): B = min(4, 5) = 4, D = min(6, 3) = 3, E = 6. Visit D (3): E = min(6, 6) = 6. Visit B (4): E = min(6, 11) = 6. Visit E (6). Shortest A → E = 6 km; path A → C → E (2 + 4 = 6) or A → C → D → E (2 + 1 + 3 = 6).
(iii) Try A → C → D → E → B → A: edges AC(2), CD(1), DE(3), EB(7), BA(4). All exist. Hamiltonian cycle A → C → D → E → B → A exists; total = 17.
Problem 4 — Postie's round
Set up. Eulerian circuit / trail check.
(i) Edges: AB, AC, BC, BD, CD, CE, DE. Degrees: A (AB, AC) = 2. B (AB, BC, BD) = 3. C (AC, BC, CD, CE) = 4. D (BD, CD, DE) = 3. E (CE, DE) = 2.
(ii) Not all even (B and D are odd). No Eulerian circuit.
(iii) Exactly 2 odd vertices ⇒ Eulerian trail exists; it must start at one odd vertex and end at the other, i.e. start at B end at D (or vice versa).
(iv) Add one edge between B and D (BD is already there, so add another, making it a multi-edge), or add edge between any two odd vertices. Simpler: add edge BD (a parallel cable, making the network a multigraph), so degrees become B = 4 and D = 4 — all even, Eulerian circuit exists. (Equivalently: remove BD, making B = 2 and D = 2 — all even, circuit exists.)
Problem 5 — Choose and solve
(i) Algorithm = MST (Kruskal's/Prim's). Sort: AB(2), HA(3), HB(4), HC(5), BC(6), AC(7). Add AB, HA, HC (→ {A,B,C,H}). Stop. MST total = 2 + 3 + 5 = $10.
(ii) Algorithm = Dijkstra's. A = 0. Visit A: B = 3, C = 7. Visit B (3): C = min(7, 5) = 5. Visit C (5). Shortest A → C = 5, path A → B → C.
(iii) Algorithm = Max-flow / min cut. S → A → T: min(5, 4) = 4. S → B → T: min(2, 3) = 2. Total = 6.