Mathematics Standard • Year 11 • Networks • Lesson 5
Minimum Spanning Trees · Master
Justify cycle rejections and compare candidate trees using total weight.
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 · Full Kruskal run. For A–F, edges AB=2, AC=5, BC=1, BD=4, CD=3, CE=6, DE=7, DF=8, EF=9. Run Kruskal. 3 marks
Q2 · Verify the tree. For the graph above, T={BC, AB, CD,CE, DF}. Verify it spans without a cycle, then find its weight. 2 marks
Q3 · Discuss uniqueness. Would tied edge weights always give a unique MST? Explain the distinction between one MST and every MST. 2 marks
Q1 · Full Kruskal run
Order BC1, AB2, CD3, BD4, AC5, CE6, DE7, DF8, EF9. Select BC, AB, CD; skip BD and AC (cycles); select CE and DF. MST total=1+2+3+6+8=20.
Q2 · Verify the tree
It forms chain A–B–C–D–E with D–F attached; all six vertices connect and no cycle occurs. Weight=1+2+3+6+8=20.
Q3 · Discuss uniqueness
No. Ties can allow different edge selections with the same minimum total, so an MST exists but may not be unique. This example has distinct weights and a unique MST.