Mathematics Standard • Year 12 • Module 5 • Lesson 8
Prim's Algorithm — Past-Paper Style
Practise HSC-style short and extended responses on Prim's algorithm, MST, and the Kruskal-vs-Prim comparison.
1. Short-answer questions
1.1 State in one sentence how Prim's avoids creating a cycle, and give the number of edges Prim's adds for a network on 11 vertices. 2 marks Band 3
1.2 Apply Prim's starting at vertex A: AB = 6, AC = 2, AD = 5, BC = 3, BD = 4, CD = 1. Show the tree and the chosen edge at each step. State the MST edges and the total. 3 marks Band 3-4
1.3 A weighted network has edges AB = 4, AC = 8, BC = 5, BD = 2, CD = 6, CE = 9, DE = 7. (a) Apply Prim's starting at E and list the MST edges and total. (b) Re-apply Prim's starting at A and list the MST edges and total. (c) In one sentence, explain why the two totals match. 4 marks Band 4
Stuck on 1.3(c)? Any minimum spanning tree of a network has the same total weight, no matter how it is found.2. Extended response
2.1 A council in regional NSW plans to connect six emergency response sites with private fibre. The cost in $thousands per direct cable is given by the table:
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 8 | 11 | — | — | — |
| B | 8 | — | 6 | 14 | 10 | — |
| C | 11 | 6 | — | 9 | — | 13 |
| D | — | 14 | 9 | — | 4 | 7 |
| E | — | 10 | — | 4 | — | 5 |
| F | — | — | 13 | 7 | 5 | — |
(a) Apply Prim's algorithm starting at A. At each step, show the current tree, list the candidate edges, and state the chosen edge.
(b) State the MST edges (in the order Prim's added them) and the minimum total cost.
(c) The council also wants to ensure that site D is connected by a direct cable to E. Check whether the MST already does this; if so, write a one-sentence conclusion. If not, state which extra edge must be added, give the new total cost, and explain in one sentence what is lost when the network is no longer a tree. 7 marks Band 5-6
Explicit marking criteria
Part (a) — 2 marks
• 1 mark — clearly tracks the tree at each step.
• 1 mark — correctly identifies candidate edges and the cheapest chosen at each step.
Part (b) — 2 marks
• 1 mark — lists 5 MST edges in addition order.
• 1 mark — correct total cost with units.
Part (c) — 3 marks
• 1 mark — checks the MST for a direct D–E cable.
• 1 mark — concludes correctly (already present or must be added with extra cost).
• 1 mark — explicit comment on "no longer a tree" (cycle created, more than n − 1 edges).
Your response:
Stuck on (c)? "Tree" requires exactly n − 1 edges; adding one more always closes a loop.How did this worksheet feel?
What I'll revisit before next class:
1.1 — Prim's, cycles and edges on 11 vertices (2 marks)
Sample response. Every Prim's edge connects a vertex already in the tree to a vertex outside, so the new vertex cannot already be reachable — no cycle is possible. Prim's adds n − 1 = 10 edges on 11 vertices.
Marking notes. 1 mark — explanation of the "outside vertex" rule. 1 mark — correct number of edges (10).
1.2 — Prim's from A on 6-edge network (3 marks)
Sample response.
{A}: AB(6), AC(2), AD(5). Add AC(2). Tree {A, C}.
{A, C}: AB(6), AD(5), BC(3), CD(1). Add CD(1). Tree {A, C, D}.
{A, C, D}: AB(6), AD(5 cycle), BC(3), BD(4). Add BC(3). Tree {A, B, C, D}. Stop.
MST: AC, CD, BC. Total = 2 + 1 + 3 = 6.
Marking notes. 1 mark — tree tracked at each step. 1 mark — candidate edges and chosen edge listed. 1 mark — correct MST and total.
1.3 — Prim's from two starting vertices (4 marks)
(a) From E. {E}: CE(9), DE(7). Add DE(7). {D,E}: CE(9), BD(2), CD(6), DE(cycle). Add BD(2). {B,D,E}: CE(9), CD(6), AB(4), BC(5). Add AB(4). {A,B,D,E}: CE(9), CD(6), AC(8), BC(5). Add BC(5). Done. MST: DE, BD, AB, BC; total = 7 + 2 + 4 + 5 = 18.
(b) From A. {A}: AB(4), AC(8). Add AB(4). {A,B}: AC(8), BC(5), BD(2). Add BD(2). {A,B,D}: AC(8), BC(5), CD(6), DE(7). Add BC(5). {A,B,C,D}: AC(8 cycle), CD(6 cycle), CE(9), DE(7). Add DE(7). Done. MST: AB, BD, BC, DE; total = 4 + 2 + 5 + 7 = 18.
(c) The minimum total weight is a property of the network — every MST has the same total weight, regardless of starting vertex or algorithm.
Marking notes. (a) 1.5 marks — Prim's steps correct, total 18. (b) 1.5 marks — Prim's steps correct, total 18. (c) 1 mark — explicit "MST weight is unique" statement.
2.1 — Emergency fibre network (7 marks): sample Band-6 response with annotations
Sample Band-6 response.
(a) Prim's from A.
{A}: candidates AB(8), AC(11). Add AB(8). Tree {A, B}.
{A, B}: candidates AC(11), BC(6), BD(14), BE(10). Add BC(6). Tree {A, B, C}.
{A, B, C}: candidates AC(cycle), BD(14), BE(10), CD(9), CF(13). Add CD(9). Tree {A, B, C, D}.
{A, B, C, D}: candidates BD(cycle), BE(10), CF(13), DE(4), DF(7). Add DE(4). Tree {A, B, C, D, E}.
{A, B, C, D, E}: candidates BE(cycle), CF(13), DF(7), EF(5). Add EF(5). Tree {A, B, C, D, E, F}. Stop. [1 mark — tree tracked; 1 mark — candidates and choice listed at each step.]
(b) MST and total cost.
MST edges (in order added): AB, BC, CD, DE, EF. [1 mark — correct edges.]
Total cost = 8 + 6 + 9 + 4 + 5 = $32 thousand. [1 mark — correct total with units.]
(c) Direct D–E cable check.
The MST already contains the edge DE(4), so site D is connected by a direct cable to site E. [1 mark — checks for D–E in MST; 1 mark — concludes "already present".]
Conclusion: the requirement is satisfied by the MST itself at total cost $32 thousand. Because the MST already meets the request, no extra edge needs to be added; the network remains a tree (5 edges on 6 vertices), and no cycle is introduced. [1 mark — explicit "no extra edge needed, still a tree" statement.]
Total: 7/7.
Band descriptors for marker.
Band 3: Lists most edges from the matrix, attempts Prim's but loses track of the tree or candidates; final cost not calculated or incorrect. ≈ 3 marks.
Band 4: Tree and candidates tracked, mostly correct edges in MST, total cost has minor arithmetic error; part (c) attempts but does not check for D–E specifically. ≈ 4-5 marks.
Band 5: Complete (a) and (b) with correct $32k total; part (c) notes D–E is in the MST but does not finish with a clear concluding sentence. ≈ 6 marks.
Band 6: All parts complete, MST correctly identified, D–E checked and conclusion explicit (with reference to "still a tree, no cycle"). 7/7.