Spanning trees and network optimisation

Spanning trees and network optimisation

Spec DB1–DB2 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A network is a graph whose arcs have weights such as distance, cost or time.
  • A spanning tree contains every node and has exactly n−1n-1 arcs; the minimum spanning tree has least total weight.
  • Kruskal's algorithm adds the lightest arcs in order, rejecting any that form a cycle.
  • Prim's algorithm grows one tree by adding the lightest arc from the tree to a node outside it.
  • An MST connects every node cheaply; it does not give the shortest route between two nodes.

The language of networks

A network is a graph with weighted arcs, and a minimum spanning tree connects every node with the least total weight.

The points are nodes (vertices) and the lines joining them are arcs (edges), each with a weight.

A tree is a connected network with no cycles. A spanning tree contains every node, and a minimum spanning tree (MST) is a spanning tree of least total weight.

Typical uses are laying cable, pipes or roads so that every site is connected using the least total length or cost.

  • Arcs in a spanning treen−1n-1 for nn nodes

A network has 9 nodes. How many arcs does a spanning tree of it have?

Kruskal's algorithm

Add the lightest arcs in order, skipping any arc that would form a cycle, until n−1n-1 arcs are chosen.

Kruskal's algorithm works across the whole network:

  1. List the arcs in ascending order of weight.
  2. Add the next arc unless it would form a cycle with arcs already chosen.
  3. Stop when n−1n-1 arcs have been chosen.

An arc is rejected only if its two nodes are already connected. Two separate pieces of tree may still be joined.

wt 6wt 4wt 5wt 7wt 3wt 2ABCDEF
Six nodes and six arcs, weights as labelled (wt = weight, not to scale).

Worked example

Use Kruskal's algorithm on the network above (6 nodes, so 5 arcs are needed).

Two arcs in a partly built tree join nodes that are in the same piece. Should Kruskal's algorithm accept the arc?

Prim's algorithm on a network

Start from any node and repeatedly add the lightest arc that joins the tree to a node outside it.

Prim's algorithm grows a single tree:

  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.

Prim's tree is always connected as it grows, whereas Kruskal's may have separate pieces until the end.

wt 12wt 8wt 9wt 10wt 7wt 11wt 6PQRST
Five nodes and seven arcs, weights as labelled (wt = weight, not to scale).

Worked example

Start at PP. Use Prim's algorithm on the network above.

In Prim's algorithm, the tree so far contains PP and RR. Which arcs may be chosen next?

Prim's algorithm on a matrix

Look only at the columns of tree nodes, in rows of nodes not yet in the tree, and choose the smallest entry each time.

A distance matrix has a row and column for each node, the entry being the arc weight.

Keep a list of nodes in the tree. At each step choose the smallest entry in the columns of tree nodes, restricted to rows of nodes not yet in the tree. That entry is the next arc. Add its node and repeat.

  1. 1

    Start at AA

    cross out its row

  2. 2

    Look at tree columns

    only rows not crossed out

  3. 3

    Circle the smallest entry

    this is the next arc

  4. 4

    Cross out the new row

    repeat until all rows are crossed out

The matrix method

Worked example

A distance matrix has rows A:(0,5,9,7)A:(0,5,9,7), B:(5,0,4,8)B:(5,0,4,8), C:(9,4,0,6)C:(9,4,0,6), D:(7,8,6,0)D:(7,8,6,0). Start at AA and find the MST.

At each step of Prim's on a matrix, where do you look for the smallest entry?

Choosing and applying the methods

Both algorithms give an MST of the same total weight, but an MST is not a shortest route between two nodes.

If arcs have equal weights the MST may not be unique, but its weight is.

If an arc becomes unavailable (a road closed), delete it and apply the algorithm again: the new MST is never lighter than the old.

An MST (a minimum connector) connects all nodes using the least total weight. It does not give the shortest route between two particular nodes: the direct arc between two nodes may be far shorter than the path through the tree.

Kruskal's

Builds:
Pieces that join up
Cycle check:
Needed
Suits:
Sorted lists of arcs

Prim's

Builds:
One growing tree
Cycle check:
Not needed
Suits:
Matrices

Does the minimum spanning tree give the shortest route between two particular nodes?

Try an exam question

A network has five nodes AA to EE and arcs ABAB 4, ACAC 7, BCBC 5, BDBD 9, CDCD 6, CECE 8, DEDE 3. Use Kruskal's algorithm to find a minimum spanning tree, giving the arcs in the order chosen and the total weight.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

How many arcs does a spanning tree of this network contain?

1 mark, marked against the mark scheme

Revision notes