Mathematics Standard • Year 11 • Networks • Lesson 5
Minimum Spanning Trees · Build
Apply Kruskal’s algorithm: order edges, avoid cycles and connect every vertex.
Practice
Unless a question says otherwise, treat each network as a simple undirected graph: edges are unordered vertex pairs, with no loops or duplicate edges. Show your reasoning in the answer space; an edge list is enough.
Q1 · Kruskal worked example. Edges are AB=1, AC=4, BC=2, BD=5, CD=3, CE=6, DE=7. Use Kruskal to find an MST. 3 marks
Q2 · Kruskal’s stopping rule. Why does Kruskal stop after selecting CE in the worked example? 2 marks
Q3 · Faded step. After selecting AB=1, BC=2 and CD=3, should AC=4 be selected? Explain. 2 marks
Q1 · Kruskal worked example
Order: AB1, BC2, CD3, AC4, BD5, CE6, DE7. Select AB,BC,CD; skip AC and BD because each makes a cycle; select CE. MST weight=1+2+3+6=12.
Q2 · Kruskal’s stopping rule
Every vertex A–E is connected then. Each additional edge would create a cycle, so the spanning tree is complete.
Q3 · Faded step
No. A, B and C are already connected; AC would form cycle A–B–C–A.