Minimum spanning trees

What you’ll learn

• Apply Kruskal’s and Prim’s algorithms.
• Read a weighted network or adjacency matrix.
• Explain the spanning-tree and minimum conditions.

Understand the idea

A spanning tree connects every vertex of a connected graph without cycles. On $n$ vertices it has $n-1$ edges. A minimum spanning tree minimises the sum of selected edge weights; it need not give the shortest route between every pair of vertices.

Kruskal's algorithm considers edges in increasing weight order and accepts an edge unless it would create a cycle. Prim's algorithm starts from one vertex and repeatedly chooses the cheapest edge joining the current tree to an unselected vertex. Record accepted and rejected edges or the changing selected set to demonstrate the method.

For an undirected network, a weighted adjacency matrix is symmetric. Distinguish a missing edge from an edge of zero cost. Prim's matrix method selects the cheapest eligible entry crossing from a selected row to an unselected column. Equal weights may give more than one minimum tree, all with the same minimum total.

Key formulae

$$|E(T)|=|V|-1$$

$$w(T)=\sum_{e\in E(T)}w(e)$$

$$a_{ij}=a_{ji}\quad\text{for an undirected network}$$

Worked example

An undirected network has vertices A, B, C, D, E and exactly these edges: AB = 2, AC = 5, BC = 1, BD = 4, CD = 3, CE = 7, DE = 2. Use Kruskal’s algorithm to find a minimum spanning tree.

1. Sort by weight: BC(1), AB(2), DE(2), CD(3), BD(4), AC(5), CE(7). Either order of the two weight-2 edges is allowed.
2. Accept BC, AB and DE: no cycle is created.
3. Accept CD to connect the ABC component to DE. All five vertices are connected using four edges.
4. Stop; the total is $1+2+2+3=8$.

Answer: Edges BC, AB, DE and CD; minimum total weight 8.