Spanning trees and network optimisationAQA A-Level Further Maths: Revision notes

A network is a graph in which every edge has a number, its weight, such as a distance, cost or time. The points are nodes (vertices) and the lines joining them are arcs (edges). A tree is a connected network with no cycles. A spanning tree is a tree that contains every node of the network, and a minimum spanning tree (MST) is a spanning tree of least total weight. A spanning tree of a network with $n$ nodes has exactly $n-1$ arcs. Typical uses are laying cable, pipes or roads so that every site is connected using the least total length or cost.

Kruskal's algorithm builds an MST by arcs, working across the whole network:

1. List the arcs in ascending order of weight.
2. Add the next arc to the tree unless it would form a cycle with arcs already chosen.
3. Stop when $n-1$ arcs have been chosen. Example: arcs $EF$ 2, $DE$ 3, $BC$ 4, $CD$ 5, $AB$ 6 are accepted; $CE$ 7 is rejected because $C$–$D$–$E$ already connects $C$ and $E$. The MST has weight $2+3+4+5+6=20$.

Prim's algorithm grows a single tree from a starting node:

1. Choose any starting node.
2. Add the lightest arc that joins a node in the tree to a node not yet in it.
3. Repeat until every node is in the tree. Starting at $P$ with $PQ$ 12, $PR$ 8, $PT$ 9, $QR$ 10, $QS$ 7, $RS$ 11, $RT$ 6 and others heavier, the arcs added are $PR$ 8, $RT$ 6, $QR$ 10, $QS$ 7, total 31. Prim's tree is always connected as it grows, whereas Kruskal's may have separate pieces until the end.

When the network is given as a distance matrix (rows and columns for nodes, the entry being the arc weight), Prim's algorithm works directly on it. Keep a list of nodes in the tree. At each step look at the columns (or rows) of the tree nodes, restricted to the rows of nodes not yet in the tree, and choose the smallest entry. That entry is the next arc. Add its node to the tree and repeat. Matrix method: start at $A$; cross out the row of each node as it joins the tree; circle the smallest uncrossed entry in the columns of tree nodes. The circled entries are the weights of the MST arcs.

Both algorithms give a minimum spanning tree with the same total weight. If arcs have equal weights the MST may not be unique, but its weight is. Kruskal's algorithm needs the arcs sorted and a cycle check; Prim's needs no cycle check and suits matrices. If an arc becomes unavailable (a road closed), delete it and apply the algorithm again: the new MST is never lighter than the old. If it was in the original tree, the weight rises (or at best stays the same). An MST connects all the nodes using the least total weight. It does not give the shortest route between two particular nodes: in a network the direct arc between two nodes may be far shorter than the path through the tree.