Minimum Spanning Trees and Kruskal’s Algorithm (AQA A-Level Further Maths): Revision Notes

Minimum Spanning Trees and Kruskal's Algorithm

What is a spanning tree?

A spanning tree (also called a connector) is a special type of sub-graph that connects all vertices in a graph without creating any cycles. It forms a tree structure that "spans" across the entire graph.

Important property of spanning trees

For any graph with $n$ vertices, a spanning tree will always have exactly $(n-1)$ edges.

This makes sense when you think about it: you need one edge to connect the first two vertices, then one more edge for each additional vertex you add, giving you $(n-1)$ edges total.

Formula: For a graph with $n$ vertices, a spanning tree has $(n-1)$ edges.

Example: different spanning trees

The same graph can have multiple different spanning trees. Here's an example showing two possible spanning trees for the same graph with six vertices (A, B, C, D, E, F):

Both diagrams show valid spanning trees because:

• They include all six vertices
• They have exactly 5 edges (since $n-1 = 6-1 = 5$)
• They contain no cycles

Minimum spanning trees

When working with weighted graphs (also called networks), where edges have numerical values representing distances, costs, or other quantities, we often want to find the spanning tree with the smallest total weight.

Why are minimum spanning trees useful?

MSTs have many real-world applications:

• Designing efficient road networks
• Planning telecommunications infrastructure
• Minimising cable lengths in electrical networks
• Optimising pipeline routes
• Reducing costs in any connected system

The challenge is that as networks get larger, the number of possible spanning trees increases dramatically. For a network with $n$ vertices, there can be $n^{n-2}$ possible spanning trees. This means we need a systematic algorithm to find the minimum one efficiently.

Kruskal's algorithm

Kruskal's algorithm provides a systematic method for finding a minimum spanning tree. It's an example of a greedy algorithm, which means at each stage you make the most advantageous choice available without thinking ahead.

The algorithm steps

Why is it called "greedy"?

Kruskal's algorithm is greedy because at each stage, you simply grab the smallest available edge that doesn't create a cycle. You don't need to plan ahead or consider future consequences—the locally optimal choice at each step leads to the globally optimal solution.

Worked example 1: applying Kruskal's algorithm

Let's find the minimum spanning tree for the following network using Kruskal's algorithm. The graph has 6 nodes (A, B, C, D, E, F), so the connector will have 5 arcs.

Worked example 2: country park problem

This example shows how Kruskal's algorithm applies to a real-world scenario.

Problem: A country park has seven picnic sites (A, B, C, D, E, F, G) and a car park, connected by rough paths. The distances between sites are shown in metres. The council wants to upgrade paths so all picnic sites are accessible by wheelchair. The upgrade costs $55 per metre. Use Kruskal's algorithm to determine which paths should be upgraded and calculate the total cost.

Exam tips

Remember!