A connected network that contains no cycles is called a tree. These have a distinctly tree-like appearance:
Once you leave a vertex on any of these networks, you can’t get back to it without repeating an edge.
We can take any connected network and remove certain edges, taking care not to disconnect the network, until we have a subnetwork that is a tree - this is then called a spanning tree. Here’s an example:
The network in the centre has its eight different spanning trees arranged around it. You can still get from one vertex to any other, but you can’t get back without repeating an edge.
A connected network that isn’t already a tree always has multiple spanning trees. This network:
This network has weight $4+6+5+2+3+10=30$4+6+5+2+3+10=30
… has $11$11 spanning trees. Here they all are, with their weights:
Weight $24$24 |
Weight $18$18 |
Weight $25$25 |
Weight $22$22 |
Weight $23$23 |
Weight $15$15 |
Weight $21$21 |
Weight $22$22 |
Weight $21$21 |
Weight $20$20 |
Weight $14$14 |
|
The last spanning tree is special, since it has the lowest weight out of all of them. We call it the minimal spanning tree. Sometimes there can be two or more spanning trees with equal lowest weight, in which case they are all minimal spanning trees.
Here’s a network with two minimal spanning trees:
Can you find both of them? It can be quite hard, and take a long time. In the next lesson we will investigate a more systematic way to find minimal spanning trees