Trees and spanning trees

Trees and spanning trees

A tree is connected and has no cycles, loops or parallel edges. A spanning tree also includes every vertex of the source graph and has the required number of edges

1. Use n minus 1 edges A tree with n vertices has exactly n − 1 edges \(\displaystyle e=n-1\)
2. Check connection and cycles The selected edges must connect every vertex and contain no cycle, loop or parallel edge
3. Check every source vertex A spanning tree uses all vertices in the source graph \(\displaystyle V_{\text{candidate}}=V_{\text{source}}\)
4. Count removals and total weight For a connected source graph with n vertices and e edges, a spanning tree removes e − (n − 1) edges. Add the weights of all retained edges to find its total weight \(\displaystyle r=e-(n-1),\qquad W(T)=\sum_{a\in T}w(a)\)

Worked example

A connected network has 6 sites and 8 connections. A spanning tree of this network has five edges with lengths 4 km, 7 km, 6 km, 5 km and 3 km. Find how many connections were removed and the total length of the spanning tree

1. \(\displaystyle n-1=6-1=5\)A spanning tree on 6 sites retains 5 edges
2. \(\displaystyle 8-5=3\)The network must lose 3 connections to retain 5 edges
3. \(\displaystyle (4+7+6+5+3)\,\text{km}=25\,\text{km}\)Add the weights of all five retained edges
4. \(\displaystyle 3\text{ connections removed},\quad 25\,\text{km}\)The spanning tree is formed after 3 removals and has length 25 km

Common mistakes

Difficulty levels

Questions about this topic

In this chapter