Minimum spanning treesEdexcel International A Level Maths: Revision notes

A tree is a connected network with no cycles. A spanning tree of a network is a tree that includes every vertex, using some of the original arcs. A network with $n$ vertices has a spanning tree with exactly $n-1$ arcs. If you add one more arc you create a cycle, and if you take one away a vertex is cut off. The minimum spanning tree (MST), also called the minimum connector, is the spanning tree with the smallest total weight. It solves problems such as connecting every site to a water, cable or road network at least cost. A network can have more than one MST when arcs have equal weights.

Kruskal's algorithm builds the MST by choosing arcs.

1. Sort the arcs into increasing order of weight.
2. Select the smallest arc.
3. Select the next smallest arc, rejecting it if it would form a cycle with arcs already chosen.
4. Repeat step 3 until $n-1$ arcs have been selected. Example: arcs $BD=3$, $AC=4$, $CE=5$, $BC=6$, $AB=7$. Accept $BD$, $AC$, $CE$, $BC$; reject $AB$ because $A$ and $B$ are already joined through $C$. Weight $=3+4+5+6=18$. Kruskal's algorithm works on the list of arcs, so it does not need a starting vertex. In the exam show the order in which you consider the arcs and write which are rejected.

Prim's algorithm grows a single tree from a starting vertex.

1. Choose any vertex to start.
2. Select the smallest-weight arc joining a vertex in the tree to a vertex not yet in the tree.
3. Repeat until every vertex is in the tree. Example: start at $A$ with arcs $AC=4$ and $AB=7$: choose $AC$. From $\{A,C\}$, arcs to new vertices are $CE=5$, $BC=6$, $AB=7$, $CD=8$: choose $CE$, then $BC$, then $BD=3$. The weight is $18$ again. The tree is built outwards, so the arcs may be chosen in a different order from Kruskal's, but the total weight of the MST is the same. Prim's algorithm is easier to apply from a table or matrix because you never need to check for cycles: you only ever add a new vertex.

A network can be shown as a distance matrix: rows and columns are labelled with the vertices, and the entry in row $X$ and column $Y$ is the weight of arc $XY$. A dash means there is no arc. The matrix is symmetrical about the leading diagonal, so each arc appears twice. To apply Prim's algorithm to the matrix:

1. Choose a starting vertex. Label its column 1 and delete (cross out) its row.
2. Look at the labelled columns, and in them circle the smallest entry in a row that is not yet deleted.
3. The circled entry gives the next arc. Label the column of the new vertex with the next number, and delete its row.
4. Repeat until all rows are deleted. The numbers 1, 2, 3, ... give the order in which the vertices are added, and the circled entries are the arcs of the MST.

To draw a network from a matrix, mark each vertex, then for each non-blank entry in the upper triangle draw one arc between those vertices and write the weight on it. Only use half of the matrix, otherwise every arc is drawn twice. To write the matrix for a network, make a square table, put each arc weight in the cell for each end (once in each triangle), and put a dash for any pair with no arc. Example: the matrix with row $P$ = $-$, 12, 9, 15, $-$ gives arcs $PQ=12$, $PR=9$ and $PS=15$, with no arc $PT$. The number of arcs equals half the number of non-blank entries. Matrix manipulation is not needed.

Always show the order in which arcs are considered or added. Marks are given for the method as well as the final weight. If two arcs have equal weight, either can be chosen, and the MST may differ but its weight will not. If an arc is forced into the tree, include it first, then continue the algorithm. The cost is at least the MST weight. When a new vertex is added, find the new MST by repeating the algorithm. Some old arcs may drop out when the new arcs offer cheaper connections.