Mathematics Standard • Year 12 • Module 5 • Lesson 7
Kruskal's Algorithm — Problem Set
Apply Kruskal's to realistic Australian planning problems: fibre rollouts, rural water mains, regional rail links and electricity grid upgrades.
Problem 1 — Mid-North-Coast fibre rollout
NBN Co plans to lay fibre between six Mid-North-Coast towns. Cable costs (in $thousands per link) are: AB = 18, AC = 22, BC = 12, BD = 25, CD = 9, CE = 16, DE = 14, DF = 20, EF = 11.
Set up: What are we solving for?
(i) Use Kruskal's algorithm. Write out the sorted edge list and then the add/reject decision for each edge. 2 marks
(ii) State the MST edges and the minimum total cost of the rollout. 2 marks
(iii) The federal government offers an extra grant if the project comes in under $80,000. Does this MST qualify? Show the comparison. 1 mark
Stuck? Revisit lesson § Card 02 — Kruskal's step-by-step.Problem 2 — Riverina water mains
An irrigation district plans to connect five pumping stations P, Q, R, S, T with new mains. Pipeline costs in $thousands: PQ = 11, PR = 8, PS = 14, PT = 17, QR = 6, QS = 10, RS = 4, RT = 13, ST = 9.
Set up: What are we solving for?
(i) Apply Kruskal's algorithm and list the MST edges. 2 marks
(ii) State the minimum total cost. 1 mark
(iii) The PR pipeline (cost $8k) is suddenly unavailable because of a heritage easement. Re-run Kruskal's without PR. Give the new MST edges and total cost. 2 marks
Stuck? Sort the remaining edges and apply Kruskal's exactly as before — just leave PR out of the sorted list.Problem 3 — Regional rail upgrade
Transport for NSW is upgrading rail links between six Hunter Valley towns. Construction costs in $millions per link: AB = 7, AC = 11, AD = 9, BC = 4, BE = 12, CD = 6, CE = 5, CF = 13, DE = 8, DF = 10, EF = 3.
Set up: What are we solving for?
(i) Use Kruskal's to find the MST. Show your sorted list and the add/reject log. 2 marks
(ii) State the minimum total cost. 1 mark
(iii) A community group argues that adding the link DE (cost $8m) on top of the MST would give a useful back-up route. State whether this would still be a tree, and give the new total cost. 2 marks
Stuck? A tree has n − 1 edges. Adding one more edge to a tree always creates a cycle.Problem 4 — Outback power grid
A solar microgrid links four communities A, B, C, D and a battery hub H. Cable costs in $thousands: AH = 6, BH = 4, CH = 7, DH = 5, AB = 8, BC = 9, CD = 10, AD = 12.
Set up: What are we solving for?
(i) Apply Kruskal's. Show the sorted list and the add/reject log. 2 marks
(ii) State the MST edges and the minimum total cost. 2 marks
(iii) Briefly explain (one sentence) why every MST edge in this network touches H. 1 mark
Stuck? Compare each "H-link" to the cheapest direct A–B, B–C, C–D, A–D edge — Kruskal's always grabs the lighter one first.Problem 5 — Ties at the council meeting
A planning department has costed five road upgrades between four suburbs: AB = 3, AC = 5, AD = 5, BC = 5, BD = 7, CD = 8.
Set up: What are we solving for?
(i) Apply Kruskal's, breaking ties by alphabetical order. State the MST edges and total. 2 marks
(ii) Show that a different tie-breaking order produces a different MST with the same total cost. List one such alternative MST. 2 marks
(iii) In one sentence, state when an MST is guaranteed to be unique. 1 mark
Stuck? Revisit lesson Activity 2 — "If all edge weights are different, is the MST unique?"How did this worksheet feel?
What I'll revisit before next class:
Problem 1 — Mid-North-Coast fibre
Set up. Apply Kruskal's to find the cheapest set of cables that links all six towns.
(i) Sort: CD(9), EF(11), BC(12), DE(14), CE(16), AB(18), DF(20), AC(22), BD(25). Add CD(9) → {C,D}. Add EF(11) → {E,F}. Add BC(12) → {B,C,D}. Add DE(14) → merges {B,C,D} and {E,F} → {B,C,D,E,F}. Reject CE(16) — forms cycle C–D–E–C. Add AB(18) → {A,B,C,D,E,F}. Stop (5 edges = n − 1).
(ii) MST edges: CD, EF, BC, DE, AB. Total = 9 + 11 + 12 + 14 + 18 = $64 thousand.
(iii) $64k < $80k, so yes — the project qualifies for the grant.
Problem 2 — Riverina water mains
Set up. Apply Kruskal's to find the cheapest set of mains that connects all five stations.
(i) Sort: RS(4), QR(6), PR(8), ST(9), QS(10), PQ(11), RT(13), PS(14), PT(17). Add RS(4) → {R,S}. Add QR(6) → {Q,R,S}. Add PR(8) → {P,Q,R,S}. Reject ST(9) — cycle. Reject QS(10) — cycle. Reject PQ(11) — cycle. Add RT(13) → {P,Q,R,S,T}. Stop (4 edges).
(ii) Total = 4 + 6 + 8 + 13 = $31 thousand.
(iii) Without PR: sort RS(4), QR(6), ST(9), QS(10), PQ(11), RT(13), PS(14), PT(17). Add RS(4), QR(6), ST(9) → {Q,R,S,T}. Reject QS(10) cycle. Add PQ(11) → {P,Q,R,S,T}. Stop. MST edges: RS, QR, ST, PQ. Total = 4 + 6 + 9 + 11 = $30 thousand. (Interesting: cheaper than the original because PR(8) was replaced by ST(9) + PQ(11) − one of the original edges.) (Marker accepts any correct alternative MST that totals $30k.)
Problem 3 — Hunter Valley rail upgrade
Set up. Apply Kruskal's to find the cheapest spanning set of rail links.
(i) Sort: EF(3), BC(4), CE(5), CD(6), AB(7), DE(8), AD(9), DF(10), AC(11), BE(12), CF(13). Add EF(3) → {E,F}. Add BC(4) → {B,C}. Add CE(5) → merges {B,C} and {E,F} → {B,C,E,F}. Add CD(6) → {B,C,D,E,F}. Add AB(7) → {A,B,C,D,E,F}. Stop (5 edges).
(ii) Total = 3 + 4 + 5 + 6 + 7 = $25 million.
(iii) Adding DE makes 6 edges on 6 vertices — no longer a tree (it now has a cycle). New total = 25 + 8 = $33 million.
Problem 4 — Outback solar microgrid
Set up. Apply Kruskal's to find the cheapest cable layout connecting all four communities and the hub H.
(i) Sort: BH(4), DH(5), AH(6), CH(7), AB(8), BC(9), CD(10), AD(12). Add BH(4) → {B,H}. Add DH(5) → {B,D,H}. Add AH(6) → {A,B,D,H}. Add CH(7) → {A,B,C,D,H}. Stop (4 edges).
(ii) MST edges: BH, DH, AH, CH. Total = 4 + 5 + 6 + 7 = $22 thousand.
(iii) Every cable to H is cheaper than every direct cable between two outer communities, so Kruskal's always picks the H-edges before any of the A–B, B–C, C–D, A–D edges. Geometrically H sits in the middle — this is a "star-shaped" MST.
Problem 5 — Ties at the council meeting
Set up. Apply Kruskal's, then show that ties allow more than one MST.
(i) Sort with alphabetical tiebreak: AB(3), AC(5), AD(5), BC(5), BD(7), CD(8). Add AB(3) → {A,B}. Add AC(5) → {A,B,C}. Reject AD(5) — wait, A and D are in different components — add AD(5) → {A,B,C,D}. Stop (3 edges). MST: AB, AC, AD; total = 3 + 5 + 5 = 13.
(ii) Alternative MST (different tiebreak — try AB, BC, AD): Add AB(3), then BC(5) → {A,B,C}, then AD(5) → {A,B,C,D}. MST: AB, BC, AD; total = 3 + 5 + 5 = 13. (Another valid alternative: AB, AC, BD does NOT work because BD = 7 is more expensive. AB, BC, BD also totals 15, not 13.)
(iii) An MST is guaranteed to be unique when all edge weights are different (no ties).