The idea, step by step
Connect all sites without cycles
A spanning tree connects every vertex without any cycle. A tree on vertices has edges. A minimum spanning tree selects the connected, cycle-free collection with the smallest total weight. It suits a cable or pipe installation when each edge has a stated installation cost.
This objective differs from finding one shortest journey. A cheap installation can leave a longer route between some sites. Explain whether the model values total installation cost, shortest travel or reliability.
Prim grows a connected set
Start at any vertex. At every step select a cheapest edge joining the existing tree to a vertex outside it. Stop when all vertices have joined. An edge whose endpoints are already included does not add a new vertex and would create a cycle.
Break ties either way. Different selections can produce the same minimum total. Record each chosen edge once and check that the final edge count is . A disconnected original network has no single spanning tree.
A common trap
Prim always takes the globally smallest unused edge.
Instead: The next edge must join the current tree to a new vertex.
See the thinking
Grow from A
Apply Prim’s algorithm to the displayed graph, starting at A.
- Choose A–C (2).
- Next C–B (1) joins B.
- Then B–D (5) joins D.
- Finally D–E (2) joins E.
- Sum .
A route need not span
Edges are A–B (1), B–C (1), A–C (3). A student selects A–B only. Is this a spanning tree?
- C is omitted from the selected connected network.
- Add B–C to connect C without a cycle.
Check your understanding
How many edges does a tree connecting 7 vertices have?
Show answer
6.
Use .
Your turn
6 questions · 12 marks · Work at your own pace.
Read the questions online
- Find a minimum spanning tree for A–B (3), A–C (4), B–C (2).2 marks
- Can all three sides of a triangle form a tree on its three vertices?2 marks
- A connected selection has 5 vertices and 4 edges. What must be checked before calling it a spanning tree of the original network?2 marks
- Prim has reached A and B. Candidates are A–C (7), B–D (5), C–D (1). What is next?2 marks
- A minimum tree costs 120 dollars. Adding a backup link between two existing vertices costs 18 dollars. Give the new cost and explain whether the selection remains a tree.2 marks
- Two spanning trees have the same minimum total 24 but different edges. Must one be wrong?2 marks
Read the worked solutions
Equivalent correct methods earn the corresponding marks. Include units where asked.
- Find a minimum spanning tree for A–B (3), A–C (4), B–C (2).2 marks
The two cheapest edges connect all vertices.
They do not create a cycle.
A–B and B–C, total 5. - Can all three sides of a triangle form a tree on its three vertices?2 marks
They form a cycle.
A three-vertex tree has two edges.
No. - A connected selection has 5 vertices and 4 edges. What must be checked before calling it a spanning tree of the original network?2 marks
Spanning means none is omitted.
Connectedness and edges then establish a tree.
That all original vertices are included. - Prim has reached A and B. Candidates are A–C (7), B–D (5), C–D (1). What is next?2 marks
C–D does not touch the current tree.
B–D is the cheapest valid joining edge.
B–D (5). - A minimum tree costs 120 dollars. Adding a backup link between two existing vertices costs 18 dollars. Give the new cost and explain whether the selection remains a tree.2 marks
.
The extra link creates a cycle and an alternative route.
138 dollars; it is no longer a tree. - Two spanning trees have the same minimum total 24 but different edges. Must one be wrong?2 marks
Tied weights can produce multiple optimum trees.
Check connectedness and the absence of cycles for each.
No.
Curriculum reference & lesson scope
SACE Board of South Australia
Stage 1 General Mathematics: matrices and networks. Original learning resources follow the approved Ascent Library chapter map.
Official curriculum source ↗