Lesson 2: Finding minimum spanning trees
Kruskal's method on the camp-site tracks
SkillFinding minimum spanning trees
Worked example
Use Kruskal's method to find a minimum spanning tree for the camp-site tracks (lengths in km), and state its weight.
Edges: 6, 4, 7, 5, 9, 3, 10, 6, 8, 4, 5, 9.
Step 1: Order the edges by weight
3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9, 10.
Step 2: Choose the first five
(3), (4), (4), (5) and (5) form no cycle. The pieces so far are and .
Step 3: Skip AB
and are already joined by –––, so (6) would make a cycle. Skip it.
A tree has no cycles, and the cheaper edges already connect to , so would be wasted.
Step 4: Choose DE
(6) joins the two pieces. That is 6 edges for 7 vertices, so stop.
A spanning tree on vertices has edges.
Step 5: Add the weights
Answer
The minimum spanning tree has edges , , , , and , with weight 27 km.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
List the edges from lightest to heaviest.
Choose each edge in turn unless it makes a cycle.
Stop at edges and add the weights.
Watch out for
Choosing as well: a seventh edge always creates a cycle.
Stopping at : is not yet joined to the rest.