Mathematics Standard • Year 11 • Networks • Lesson 4
Trees & Spanning Trees · Apply
Choose a connected, cycle-free set of links that reaches every site.
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 · Sensor stations. Stations A–E have links AB,AC,BC,CD,CE,DE. Select a spanning tree and explain why it spans. 3 marks
Q2 · Remove a cycle edge. For the same network, is {AB,BC,AC,CD,CE} a tree? If not, remove one edge to make a spanning tree. 2 marks
Q3 · Compare two choices. Are T1={AB,AC,CD,CE} and T2={AB,BC,CD,DE} both spanning trees for the five stations? 2 marks
Q1 · Sensor stations
{AB,AC,CD,CE} connects all five stations and contains no cycle.
Q2 · Remove a cycle edge
No: A–B–C–A is a cycle. Remove BC; {AB,AC,CD,CE} remains connected and acyclic.
Q3 · Compare two choices
Yes. T1 connects all vertices without a cycle; T2 is the chain A–B–C–D–E, also connected and acyclic.