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).