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.
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.
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:
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.
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.
Want to suggest an edit? Have some questions? General comments? Let us know how we can make this resource more useful to you.