Minimum spanning treesEdexcel A-Level Further Maths: Revision notes

A spanning tree connects every vertex of a network with no cycles. A minimum spanning tree (minimum connector) is a spanning tree with the smallest possible total weight. It answers questions such as: what is the cheapest set of cables, pipes or roads that joins all the sites? A network with $n$ vertices has a spanning tree with exactly $n-1$ edges. If all the weights are different, the minimum spanning tree is unique. If some weights are equal, there may be more than one. Two algorithms find it: Kruskal's and Prim's.

Kruskal's algorithm works on the list of edges.

1. Sort the edges in increasing order of weight.
2. Take the next edge. Accept it unless it would form a cycle with the edges already accepted, in which case reject it.
3. Stop when $n-1$ edges have been accepted. Example (six vertices, edges $DE=3$, $AC=4$, $CD=5$, $BC=6$, $AB=7$, $CE=8$, $BD=9$, $EF=10$, $DF=12$): accept $DE$, $AC$, $CD$, $BC$; reject $AB$ (cycle $ABC$), $CE$ (cycle $CDE$) and $BD$ (cycle $BCD$); accept $EF$. That is 5 edges with total $3+4+5+6+10=28$.

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

1. Choose any vertex to start the tree.
2. Look at all edges joining a vertex in the tree to a vertex not in the tree. Add the one of smallest weight.
3. Repeat until all vertices are in the tree. Example with edges $AB=6$, $AC=9$, $BC=4$, $BD=8$, $CD=7$, $CE=5$, $DE=3$ starting at $A$: add $AB(6)$, then $BC(4)$, then $CE(5)$, then $ED(3)$. The total is 18. The tree is always connected as it grows, so cycles can never form.

When a network is given as a distance matrix, Prim's algorithm is applied directly to it.

1. Choose a start vertex. Number its column 1 and delete its row.
2. Look at the numbered columns. Among the entries in the rows not yet deleted, choose the smallest and circle it.
3. The row of the circled entry is a new vertex. Number its column next, and delete its row.
4. Repeat until all rows are deleted. The circled entries are the arcs of the tree. In the $5\times5$ matrix for the example above, starting at $A$ gives circled entries $AB=6$, $BC=4$, $CE=5$, $ED=3$. Read the arcs in the order of the column numbers.

You may be asked to draw a network from a matrix or to write down the matrix of a network.

• For an undirected network the matrix is symmetric: the entry in row $X$, column $Y$ equals the entry in row $Y$, column $X$.
• A dash (or blank) means there is no direct edge. Each edge appears twice, once above and once below the leading diagonal.
• To count edges, count the numerical entries on one side of the diagonal.
• To draw the network, plot a vertex for each row and join $X$ to $Y$ with an edge labelled with the entry whenever it is a number. Removing an edge from the network changes the tree only if that edge was in it. Replace it with the cheapest remaining connection to the vertex it served.