Mathematics Standard • Year 11 • Networks • Lesson 5
Minimum Spanning Trees · Apply
Find the least-total-weight set of links that connects every location.
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 · Rural fibre links. Potential links are PQ=2, PR=6, QR=3, QS=5, RS=4, RT=7, ST=1. Use Kruskal. 3 marks
Q2 · Unavailable link. In the same network, RS=4 is unavailable. Find an MST and its total weight. 2 marks
Q3 · Explain the objective. Why use a spanning tree instead of choosing only the cheapest link? 2 marks
Q1 · Rural fibre links
Order: ST1, PQ2, QR3, RS4, QS5, PR6, RT7. Select ST, PQ, QR, RS, connecting all vertices. MST total=1+2+3+4=10.
Q2 · Unavailable link
Select ST1, PQ2, QR3, QS5: they connect all vertices with no cycle. Total=11.
Q3 · Explain the objective
A single edge does not connect every location. A spanning tree reaches every vertex without redundant cycles, while minimizing total weight.