# 7.01 Trees and spanning trees

Lesson

## 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.

#### Practice questions

##### Question 1

Given the following networks:

1. Which of these networks is a tree?

A

B

C

A

B

C
2. Why is the following network not a tree?

It is disconnected.

A

It has a circuit.

B

It has multiple edges connecting the same vertices.

C

It has a loop.

D

It is disconnected.

A

It has a circuit.

B

It has multiple edges connecting the same vertices.

C

It has a loop.

D
3. Why is the following network not a tree?

It has a loop.

A

It has multiple edges connecting the same vertices.

B

It is disconnected.

C

It has a circuit.

D

It has a loop.

A

It has multiple edges connecting the same vertices.

B

It is disconnected.

C

It has a circuit.

D

##### Question 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.

## Spanning trees

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.

#### Practice question

##### Question 3

Does the following network have a spanning tree?

1. Yes

A

No

B

Yes

A

No

B

A connected network that isn’t already a tree can have multiple spanning trees. The network below has $11$11 possible spanning trees:

This network has weight $4+6+5+2+3+10=30$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$n vertices will have $(n-1)$(n1) edges.

 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

## Minimal spanning trees

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 sections we will investigate a more systematic way to find a minimal spanning tree.

#### Practice question

##### Question 4

Consider the given weighted network to the right. Which of the following networks is the minimal spanning tree?

1. A

B

C

D

A

B

C

D

## Prim's algorithm from a network

Sometimes it is going to be very impractical to find a minimal spanning tree by eye. The following network represents a mycorrhizal nutrient transfer system:

These underground connections are created and maintained by the fungus to connect and nurture the roots of plants (represented here by the vertices) under the ground. The weights represent distance in metres.

A severe drought is affecting the area, so only the most essential connections can be sustained by the fungus. What is the shortest total distance that the mycorrhizal network needs to spread itself across, while still making sure that every plant is connected to every other one?

We need to find the minimal spanning tree. This particular network has $416$416 spanning trees, which one is minimal? Feel free to find them all and add up all their weights, but it’s going to take a very long time.

Instead, we’re going to use a procedure called Prim’s Algorithm to find the minimal spanning tree without having to find all the spanning trees. The algorithm was first created by Vojtěch Jarník, a Czech mathematician, in 1930. Both Robert Prim (in 1957) and Edsger Dijkstra (in 1959) independently rediscovered it, though Prim’s work popularised its use.

We begin by picking a vertex, any vertex will do. Let’s say we pick $F$F. We then highlight the lowest weight edge coming out of $F$F:

We then add this edge, and the vertex on the other side, to our spanning tree:

Then we do the same thing again! Highlight the edge of lowest weight coming out of our spanning tree:

The vertex $F$F was just a starting point - the lowest weight edge connected to the spanning tree comes out of $E$E, now.

We then add that edge, and its vertex, to the spanning tree:

Once again, we highlight the lowest weight edge coming out of the spanning tree:

This time, there are two candidates! Both $DC$DC and $DF$DF have weight $12$12. However, $DF$DF cannot be used because that would create a loop.

The lowest weight edge coming out of the spanning tree is still the weight $12$12 edge $DF$DF:

However, we are going to reject this edge, since adding it to our spanning tree would create a cycle, and trees can’t have cycles.

Edges connecting vertices already in the spanning tree will always be rejected.

We won’t ever consider the edge $DF$DF again. So we move on to highlight the next lowest weight edge:

This edge doesn’t create a cycle, so we add it into the growing spanning tree:

The next lowest weight edges are all weight $14$14 so we highlight them all:

Once again, we reject the edge $DB$DB since it would create a cycle:

That leaves us with two choices:

We are free to pick either of these. We add in the edge and the vertex, growing the spanning tree by one vertex every step:

Instead of going back to the edge $EG$EG of weight $14$14, we now have an edge connected to our spanning tree of lower weight:

We add that in as before, and highlight the lowest weight edge connecting the spanning tree to our final vertex:

We add this edge and vertex into the network, completing the procedure:

We can delete the unused edges for a clearer picture of our final result:

Our fungus spanning tree has grown from the vertex $F$F to cover every plant in the area, and it covers $12+10+10+13+14+8+7=74$12+10+10+13+14+8+7=74 metres in total.

This procedure is guaranteed to find the minimal spanning tree every time. Much easier than finding all the spanning trees and adding up all their weights! Here’s a summary of the procedure.

Prim’s algorithm (from a network):
1. Pick any vertex to start the spanning tree.
2. Locate the lowest weight edge connected to the spanning tree.
3. If this edge would create a cycle, reject it.
4. If there is more than one edge with the lowest weight, pick any of them.
5. Add this edge and the vertex at the other end to the spanning tree. If all vertices are part of the spanning tree, stop. Otherwise, repeat from step 2.

#### Practice questions

##### Question 5

The rangers of a national park want to clear walking tracks to $6$6 landmarks in the area. The potential tracks between landmarks are shown in the graph below, along with the number of days required to clear each track for use.

To make a network of tracks in the shortest time, the rangers want to find a minimal spanning tree for the graph.

1. Which two of the following are possible minimal spanning trees?

A

B

C

D

A

B

C

D
2. What is the minimum time taken to build a network of tracks that connect each landmark?

##### Question 6

The direct flight routes between $5$5 major cities of the same country are shown in the graph below. Each edge is marked with the distance (in km) travelled on each route.

To optimise the investment put into these routes, the operating airline wants to find the minimum spanning tree for the graph.

1. How many edges will be a part of a spanning tree for this graph?

2. Using Prim's algorithm or otherwise, find a minimum spanning tree for the graph.

Which of the following edges are part of this spanning tree? Select all that apply.

$DE$DE

A

$AB$AB

B

$BC$BC

C

$AE$AE

D

$BD$BD

E

$CE$CE

F

$DE$DE

A

$AB$AB

B

$BC$BC

C

$AE$AE

D

$BD$BD

E

$CE$CE

F
3. Select the diagram which represents the minimum spanning tree.

A

B

C

D

A

B

C

D
4. Using these flight routes, what is the minimum distance connecting these major cities?

### Prim's algorithm from a table

The example in the previous section showed how we can use Prim's algorithm with a weighted network. Alternatively, we can use this algorithm with a distances table.

The network from the previous example is repeated here:

This network corresponds to a distances table that shows the distances between each pair of adjacent vertices.

Table 1

The network is not a directed network so the distances table is symmetric about the diagonal. That is, the distance from $A$A to $B$B is the same as the distance from $B$B to $A$A, and so on.

With this table, we can now work through the columns to connect vertices to our minimum spanning tree. It doesn't matter which vertex we start at (because they will all be connected in the end), so we will start on the left with vertex $A$A. This becomes the first vertex on the minimum spanning tree, highlighted with the box, in the heading row of Table 2.

Table 2

Since $A$A is part of the spanning tree, we can scan down only column $A$A to find connections that can be added. We can see that the edge $A-G$AG is $8$8 metres and, since this is the shortest possible edge to a new vertex, $G$G will be the next node added to the spanning tree.

Table 3

In Table 3, both $A$A and $G$G are boxed to show that they are connected to the spanning tree. Rows for $A$A and $G$G are shaded out because we do not want to add any other edges to these vertices - that would create a circuit. When we do this working on paper we could strike out these rows by drawing a line, and we don't need to redraw the table for each step.

The table cells that are not shaded, in the $A$A and $G$G columns show the possible new connections. We need to look down only columns $A$A and $G$G to find the next shortest possible connection to the spanning tree. The new connection is circled red, showing that we should next use the edge $G-H$GH to connect vertex $H$H.

Table 4

In Table 4 we have vertices $A$A, $G$G and $H$H connected to the spanning tree, indicated with a box around the column heading. The rows for these vertices are shaded (or crossed out) so we don't create loops and we can now look down only columns $A$A, $G$G and $H$H (the unshaded columns) for the next lowest edge weight. We can select the edge $G-E$GE, with a weight of $14$14. Note that this was not the only possible choice - the edge $A-B$AB also has a weight of $14$14. It doesn't matter which one we select. The minimum spanning tree is not always unique.

Table 5

Table 5 shows that vertices $A$A, $E$E, $G$G and $H$H are now connected. Look down only these $4$4 columns to find the next selected edge is $E-D$ED, with weight $10$10 (again there was another possible choice of $E-F$EF).

Table 6

Vertices $A$A, $D$D, $E$E, $G$G and $H$H are now connected. Look down only these $5$5 columns and this time time we will choose $E-F$EF.

Table 7

Vertices $A$A, $D$D, $E$E, $F$F, $G$G and $H$H are now connected. We choose $D-C$DC.

Table 8

We add edge $F-B$FB so that $B$B becomes the final vertex added to the network.

Table 9

Having connected all the vertices we now have constructed a minimum spanning tree for this network. Other than the starting vertex, every row should have exactly one table cell selected because every vertex in a tree is connected by a single edge.

The network for the minimum spanning tree can be extracted from Table 9, and will look like this:

Notice that this is not exactly the same as the previous example when the spanning tree was identified from the network. The difference is a result of our choice to connect edge $G-E$GE instead of $A-C$AC, which both had a weight of $14$14.

We can still see that the total distance is minimised: $12+10+10+13+14+8+7=74$12+10+10+13+14+8+7=74 metres.

If the network for which we need to find the minimum spanning tree is specified in table form then this algorithm will be most efficient. For small to moderate-sized networks given with a graphical representation, it is usually easy enough to find the minimum spanning tree graphically.

Both the graphical and table methods require working methodically to ensure that the shortest edge is identified at each stage.

Prim’s algorithm (from a table):
1. Pick any vertex to start the spanning tree and highlight the column header.
2. Strike-out the row corresponding to the newly connected vertices.
3. Locate the lowest weight edge from the columns of connected vertices.
4. If there is more than one edge with the lowest weight, pick any of them.
5. Add this edge by highlighting the column header and striking out the row. If all vertices are part of the spanning tree, stop. Otherwise, repeat from step 3.

#### Practice questions

##### Question 7

Find the total length of the minimum spanning tree for the network represented by the distance table shown below.

### Outcomes

#### ACMGM101

explain the meaning of the terms tree and spanning tree identify practical examples

#### ACMGM102

identify a minimum spanning tree in a weighted connected graph either by inspection or by using Prim’s algorithm

#### ACMGM103

use minimal spanning trees to solve minimal connector problems; for example, minimising the length of cable needed to provide power from a single power station to substations in several towns