Minimal Spanning Trees Revision Notes for HSC SSCE Mathematics Standard

Minimal Spanning Trees

In many network problems, we need to find the most efficient way to connect all points in a graph. Think about connecting multiple towns to a water supply network - we want to ensure every town has access, but we also want to minimise the cost of laying pipes. This is where minimal spanning trees become useful.

To understand minimal spanning trees, we first need to understand what trees are in graph theory.

What is a tree?

A tree is a connected graph that contains no cycles, multiple edges or loops.

infoNote

Let's break down what this means:

Connected: There is a path between any two vertices
No cycles: You cannot start at a vertex and return to it by following edges
No multiple edges: There is at most one edge between any two vertices
No loops: No edge connects a vertex to itself

In the diagram above, Graphs 1 and 2 are trees because they are connected and have no cycles, multiple edges or loops. Graph 3 is not a tree because it contains several cycles, including a loop (an edge from a vertex to itself) and multiple edges (more than one edge connecting the same pair of vertices).

Key property of trees

Trees have a special relationship between the number of vertices and the number of edges:

chatImportant

A tree with $n$ vertices has $n - 1$ edges.

This property helps you:

Identify whether a graph is a tree
Construct spanning trees correctly
Check your work when finding spanning trees

For example:

A tree with $8$ vertices has $7$ edges
A tree with $11$ vertices has $10$ edges

In other words, the number of edges is always one less than the number of vertices.

Spanning trees

Every connected graph contains at least one subgraph that is a tree. When this tree subgraph connects all the vertices in the original graph, it is called a spanning tree.

A spanning tree is a tree that connects all of the vertices of a graph.

There are often multiple possible spanning trees for a given graph. As long as the tree connects all vertices and contains no cycles, it qualifies as a spanning tree.

Minimum spanning trees

When working with weighted graphs (graphs where each edge has a numerical value or "weight"), we can calculate the total length of a spanning tree by adding up all the weights of its edges.

For the spanning tree shown above: $\text{Length} = 5 + 4 + 2 + 1 + 5 + 4 + 1 = 22 \text{ units}$

A minimum spanning tree is a spanning tree of minimum length. It connects all the vertices together with the minimum total weighting for the edges.

infoNote

Real-World Applications

The weights in a graph might represent:

Costs of installing connections
Distances between locations
Time taken to travel between points

Finding the minimum spanning tree ensures we achieve our goal (connecting all vertices) in the most efficient way possible.

Finding spanning trees: worked example

Let's practice finding spanning trees for a graph.

lightbulbExample

Worked Example: Finding Two Spanning Trees

Problem: Find two spanning trees for the given graph.

The graph has five vertices labelled $A$ , $B$ , $C$ , $D$ , and $E$ , with seven edges connecting them.

Solution:

Step 1: Count the vertices and edges.

The graph has five vertices
A spanning tree will have five ( $n$ ) vertices and four ( $n - 1$ ) edges

Step 2: Form the first spanning tree. To create a spanning tree, we need to remove three edges from the original seven edges, making sure:

All five vertices remain connected
No cycles are created
No multiple edges or loops exist

Spanning Tree 1: Remove edges $EB$ , $ED$ and $CA$

This leaves us with edges $EA$ , $AB$ , $BD$ , and $DC$ , connecting all five vertices without forming any cycles.

Step 3: Form a second spanning tree. We can create a different spanning tree by removing a different set of three edges.

Spanning Tree 2: Remove edges $EA$ , $AC$ and $CD$

This leaves us with edges $EB$ , $AB$ , $BD$ , and $DC$ , again connecting all five vertices without cycles.

There are several other possible spanning trees for this graph - try finding some yourself!

Prim's algorithm

Prim's algorithm is a systematic method for finding a minimum spanning tree in a weighted graph. It works by building the tree one edge at a time, always choosing the edge with the smallest weight that doesn't create a cycle.

Steps in Prim's algorithm

Step 1: Choose any starting vertex (it doesn't matter which one).

Step 2: Look at all edges connected to the starting vertex. Select the edge with the lowest weight. If multiple edges have the same lowest weight, choose any one of them. You now have two vertices and one edge in your tree.

Step 3: Look at all edges connected to any vertex currently in your tree. Select the edge with the lowest weight, but ignore any edges that would create a cycle (connecting the tree back to itself). You now have three vertices and two edges in your tree.

Step 4: Repeat Step 3 until all vertices are included in the tree.

The result is a minimum spanning tree for the graph.

Worked example: Prim's algorithm

lightbulbExample

Worked Example: Applying Prim's Algorithm

Problem: Apply Prim's algorithm to find the minimum spanning tree for the network graph shown. Calculate the length of the minimum spanning tree.

The graph has six vertices ( $A$ , $B$ , $C$ , $D$ , $E$ , $F$ ) with weighted edges.

Solution:

Step 1: Start with vertex $A$ .

List the weighted edges from vertex $A$ and find the smallest:

$(A, B) = 2$
$(A, F) = 6$

The lowest weight is $(A, B) = 2$ . Add edge $AB$ to the tree.

Step 2: Look at vertices $A$ and $B$ .

List all weighted edges from vertices $A$ and $B$ (excluding edge $AB$ which we've already added):

$(A, D) = 5$
$(A, F) = 6$
$(B, C) = 8$
$(B, D) = 6$

The lowest weight is $(A, D) = 5$ . Add edge $AD$ to the tree.

Step 3: Look at vertices $A$ , $B$ and $D$ .

Find the smallest weighted edge from any of these vertices (excluding edges already in the tree):

$(A, F) = 6$
$(B, C) = 8$
$(B, D) = 6$ (already connected via $A$ , would create cycle)
$(C, D) = 3$

The lowest weight is $(C, D) = 3$ . Add edge $CD$ to the tree.

Step 4: Look at vertices $A$ , $B$ , $C$ and $D$ .

Find the smallest weighted edge:

$(A, F) = 6$
$(B, C) = 8$ (would create cycle)
$(C, E) = 5$

The lowest weight is $(C, E) = 5$ . Add edge $CE$ to the tree.

Step 5: Look at vertices $A$ , $B$ , $C$ , $D$ and $E$ .

Find the smallest weighted edge from these vertices that includes vertex $F$ :

$(A, F) = 6$
$(E, F) = 2$

The lowest weight is $(E, F) = 2$ . Add edge $EF$ to the tree.

Step 6: All vertices are now connected.

The minimum spanning tree consists of edges: $AB$ , $AD$ , $CD$ , $CE$ , and $EF$ .

Step 7: Calculate the length.

Add the weights of all edges in the minimum spanning tree: $\text{Length} = 2 + 5 + 3 + 5 + 2 = 17 \text{ units}$

The minimum spanning tree has a total length of $17$ units.

chatImportant

Exam Tip

When applying Prim's algorithm, keep a clear list of which vertices are already in your tree. This helps you avoid accidentally creating cycles by choosing edges that connect two vertices already in the tree.

Alternative method

There is another algorithm called Kruskal's algorithm that can also be used to find minimum spanning trees. While we haven't covered it in detail here, it's worth knowing it exists as an alternative approach.

bookmarkSummary

Key Points to Remember:

A tree is a connected graph with no cycles, loops, or multiple edges. For a tree with $n$ vertices, there are always $n - 1$ edges.
A spanning tree connects all vertices in a graph while maintaining the properties of a tree. Different spanning trees can exist for the same graph.
A minimum spanning tree is the spanning tree with the smallest total edge weight, making it the most efficient way to connect all vertices in a weighted graph.
Prim's algorithm builds a minimum spanning tree step by step by always selecting the lowest-weight edge that doesn't create a cycle, starting from any vertex and continuing until all vertices are connected.
To find the length of any spanning tree, simply add up the weights of all edges in the tree.

Minimal Spanning Trees (HSC SSCE Mathematics Standard): Revision Notes