7.01 Trees and spanning trees

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.

Examples

Example 1

Which of these networks is a tree?

A

B

C

Worked Solution

Create a strategy

Choose the network that does not contain cycles or loops.

Apply the idea

The answer is option B since it does not have a cycle or a loop.

Example 2

Sarah has three children: Kate, Matt, and Tom. Kate has four children, Lisa, Sandy, Amy, and Robert, and Matt has two sons, Joseph and Chris. Both Tom and Lisa have one child each: Barbara and Alex, respectively. If the starting vertex represents Sarah, create a tree to represent the parent-child relationships in this family.

Worked Solution

Create a strategy

Use the given vertex as the starting point of the tree. Connect each vertex to that person's children.

Apply the idea

Connect the first vertex that represents Sarah to 3 vertices that represent her children Kate, Matt, and Tom.

Next, connect Kate's vertex to 4 vertices that represent her children: Lisa, Sandy, Amy, and Robert. Connect Lisa's vertex to the vertex that represents her child, Alex.

From Matt, connect to the 2 vertices that represent his children: Joseph and Chris.

From Tom, use an edge to connect to a vertex that represents his child, Barbara.

A spanning tree is a subnetwork of a connected network that is also a tree. It has no cycles or loops.

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 can have multiple spanning trees. The network below has 11 possible spanning trees:

This network has weight 4+6+5+2+3+10=30.

Here are all the spanning trees, with their weights. Notice that all the spanning trees have the same number of edges. The spanning tree for a network with n vertices will have (n-1) edges.

Examples

Example 3

Does the following network have a spanning tree?

Worked Solution

Create a strategy

Check whether all the vertices are connected or have a path.

Apply the idea

Vertices D and E are disconnected from vertices A,B, and C. So it does not have a spanning tree.

The last spanning tree in the previous example is special because 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 following lesson we will investigate a more systematic way to find a minimal spanning tree.

Examples

Example 4

Consider the given weighted network.

Which of the following networks is the minimal spanning tree?

A

B

C

D

Worked Solution

Create a strategy

Add the weights of edges from each option to find the one with the lowest total weight.

Apply the idea

Firstly we much check that each option spans the entire network. In each option, all vertices A to F are included, so each is a spanning tree. Now we can compare their weights.

\displaystyle \text{Total weight (A)}	\displaystyle =	\displaystyle 6+1+7+6+5	Add the weights of the edges
	\displaystyle =	\displaystyle 25	Evaluate
\displaystyle \text{Total weight (B)}	\displaystyle =	\displaystyle 1+3+7+6+5	Add the weights of the edges
	\displaystyle =	\displaystyle 22	Evaluate
\displaystyle \text{Total weight (C)}	\displaystyle =	\displaystyle 1+3+7+9+5	Add the weights of the edges
	\displaystyle =	\displaystyle 25	Evaluate
\displaystyle \text{Total weight (D)}	\displaystyle =	\displaystyle 1+3+10+6+5	Add the weights of the edges
	\displaystyle =	\displaystyle 25	Evaluate

Since option B has the lowest total weight of 22, it has the minimal spanning tree of the given network.