Tree

A tree is a connected graph that contains NO circuits or loops.

Essential Further Mathematics 4ed 2012 (Fig 23.21)

NOTE: A tree with ‘n’ vertices has n – 1 edges.

Spanning Tree

A spanning tree is a network in which all vertices are connected and there are no circuits. It contains all the vertices of the original graph.

Essential Further Mathematics 4ed 2012 (Fig 23.22)

Essential Further Mathematics 4ed 2012 (Fig 23.23)

*Figure 23.23 is the spanning tree of Figure 23.22

The numbers that are on the edges of the above graphs represents weights. These numbers may represent distance, volume of traffic or even litres of water. You will need to look at the context that the graph is being used in, to decide what the numbers represent.

Minimum Spanning Tree

Like its name suggests a minimum spanning tree is a spanning tree where the sum of all the weights on the edges is as small as possible.

To find a minimum spanning tree, an easier method to use than using Prim’s Algorithm is to:

• Find the lowest weight on an edge and then work your way up until a spanning tree is obtained.
• It is a matter of trial and error.

Essential Further Mathematics 4ed 2012 (Example 8 p.630)

In the above example, the lowest weight is 2. However there are two of them (A to B and F to E), so we choose them both. (To make it easier you should highlight those edges so it makes it clear to you that you are going to pick them).

Next, you choose the next biggest number after 2. In this case it is 3 (C to D).

You would keep finding the next biggest number after the previous number, until you have a spanning tree. In the end it should look like this:

The total weight for this graph is 17 (2 + 5 + 3 + 5 + 2).

You would repeat the process until all the vertices are connected together. It is a matter of trial and error, especially if you have two edges that have the same weight.

In summary:

1. Find the edge with the lowest weight. If there is more than one then pick both.
2. Choose the next edge that has the next smallest number after the first edge(s) that you pick.
3. Repeat the process (by choosing the next biggest number after the previous one) until you end up with a connected graph (Spanning tree).

REMEMBER: A spanning tree DOES NOT have any circuits, if you end up with a circuit after going through the process, then you must start again even if the subsequent trees that you find has a bigger total weight than your first tree with the circuit.