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

Any connected network can have edges removed, taking care not to disconnect the network, until the result is 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 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.

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.

Examples

Example 1

Consider the following graphs.

a

Which of these networks is a tree?

A

B

C

Worked Solution

Create a strategy

Choose a network that does not consist of any loops and cycles (a path that ends where it starts).

Apply the idea

Among the choices, only Option C is a network that does not consist of any loops and cycles as it only passes through each of its vertex only once. So, this means that Option C is a tree.

Watch question walkthrough

b

Why is the following graph not a tree?

A

It is disconnected.

B

It has a loop.

C

It has multiple edges connecting the same vertices.

D

It has a cycle.

Worked Solution

Create a strategy

Consider the definition of a cycle to determine why this particular graph is not a tree.

Apply the idea

Among the choices, the given graph is not a tree because it has a cycle. Based on the given graph, it has a path that starts and ends at the same vertex passing through successive vertices.

So, the correct answer is Option D.

Watch question walkthrough

c

Why is the following graph not a tree?

A

It has a loop.

B

It is disconnected.

C

It has a cycle.

D

It has multiple edges connecting the same vertices.

Worked Solution

Create a strategy

Consider the definition of a loop and disconnected graph to determine why this particular graph is not a tree.

Apply the idea

Based on the given graph, it is a disconnected as there are pairs of vertices (ABC and DEF) that are not connected by any path. Moreover, the graph has a cycle as there are paths that start and finish at the same vertex.

So, the correct answers are Options B and C.

Watch question walkthrough

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 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 Vojtech 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. We then highlight the lowest weight edge coming out of 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 was just a starting point - the lowest weight edge connected to the spanning tree comes out of E, now.

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

\,

Once again, we highlight the lowest weight edges coming out of the spanning tree.

This time, there are two candidates. Both DC and DF have weight 12.

However, DF cannot be used because that would create a loop. So we include the edge DC.

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

Now we move on to highlight the next lowest weight edge connected to our spanning tree which is BF.

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 so we highlight them all.

Once again, we reject the edge 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 of weight 14, we now have an edge connected to our spanning tree of lower weight, AG.

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 to cover every plant in the area, and it covers 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.

Examples

Example 2

The rangers of a national park want to clear walking tracks to 6 landmarks in the area. The potential tracks between landmarks are shown in the graph, 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.

a

Which two of the following are possible minimal spanning trees?

A

B

C

D

Worked Solution

Create a strategy

Use the Prim's Algorithm to test each option.

Apply the idea

All the spanning trees seem to have started from vertex A. From vertex A we could move to either B or F since both edges AB and AF have a weight of 7.

If we move to vertex B, we would move to vertex E then D then C by following the edges with the lowest weights. We still need to connect to vertex F so we would also include the edge EF since its weight is lower than the weight of AF. This tree corresponds to option C, and has a total weight of: 7+4+2+6+6=25.

If we move to vertex F, we would move to vertex E then D then C by following the edges with the lowest weights. We still need to connect to vertex B so we would also include the edge EB since its weight is lower than the weights of AB, CB and DB. This tree corresponds to option A, and has a total weight of: 7+6+4+2+6=25.

So the possible minimal spanning trees are in options A and C.

Watch question walkthrough

b

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

Worked Solution

Create a strategy

Add the weights of edges of the minimum spanning trees found in part (a).

Apply the idea

In part (a) we found that the total weight of both minimal spanning trees was 25.

The minimum time taken to build a network of tracks is 25 days.

Watch question walkthrough