What is a minimum spanning tree?

A spanning tree of least total weight.

State Kruskal's algorithm.

Take arcs in ascending order of weight, rejecting any that form a cycle, until n-1 arcs are chosen.

State Prim's algorithm.

Start at any node; repeatedly add the lightest arc joining a node in the tree to a node not in it.

When is an arc rejected in Kruskal's algorithm?

When its two nodes are already connected, so it would form a cycle.

What do node, arc and weight mean?

Node: a point. Arc: a line joining two nodes. Weight: the number on an arc (distance, cost or time).

Do Kruskal's and Prim's give the same total weight?

Yes: both give a minimum spanning tree.

Is a minimum spanning tree always unique?

No: equal weights can give different trees, but the total weight is the same.

How does Prim's algorithm work on a matrix?

Choose the smallest entry in the columns of tree nodes among rows of nodes not yet in the tree.

What should you do if an arc in the network is closed?

Remove it and re-apply the algorithm to the remaining arcs.

Does an MST give the shortest route between two nodes?

No: it minimises total weight of the whole tree, not distances between pairs.

Spanning trees and network optimisationAQA A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

What is a spanning tree?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

What is a spanning tree?: A connected network with no cycles that contains every node of the network.
How many arcs has a spanning tree on $n$ nodes?: $n-1$
What is a minimum spanning tree?: A spanning tree of least total weight.
State Kruskal's algorithm.: Take arcs in ascending order of weight, rejecting any that form a cycle, until $n-1$ arcs are chosen.
State Prim's algorithm.: Start at any node; repeatedly add the lightest arc joining a node in the tree to a node not in it.
When is an arc rejected in Kruskal's algorithm?: When its two nodes are already connected, so it would form a cycle.
What do node, arc and weight mean?: Node: a point. Arc: a line joining two nodes. Weight: the number on an arc (distance, cost or time).
Do Kruskal's and Prim's give the same total weight?: Yes: both give a minimum spanning tree.
Is a minimum spanning tree always unique?: No: equal weights can give different trees, but the total weight is the same.
How does Prim's algorithm work on a matrix?: Choose the smallest entry in the columns of tree nodes among rows of nodes not yet in the tree.
What should you do if an arc in the network is closed?: Remove it and re-apply the algorithm to the remaining arcs.
Does an MST give the shortest route between two nodes?: No: it minimises total weight of the whole tree, not distances between pairs.

Exam questions on Spanning trees and network optimisation

A network has six nodes $A$ to $F$ . The arcs and their weights are $AB$ 6, $AC$ 9, $BC$ 4, $BD$ 8, $CD$ 5, $CE$ 7, $DE$ 3, $DF$ 10 and $EF$ 2.
Explain why Kruskal's algorithm rejects arc $CE$ .2 marks
Five villages $P,Q,R,S,T$ are to be linked by cables. The possible links and their costs, in hundreds of pounds, are $PQ$ 12, $PR$ 8, $PS$ 15, $PT$ 9, $QR$ 10, $QS$ 7, $QT$ 14, $RS$ 11, $RT$ 6 and $ST$ 13.
Explain why Prim's algorithm starting at $P$ does not select arc $QS$ , with weight 7, until the last step, even though it is lighter than arc $PR$ .2 marks
Five towns $A$ to $E$ are to be connected by cable laid along direct links. The distances in km between the towns, with rows and columns in the order $A,B,C,D,E$ , are given by $\begin{pmatrix} 0&5&9&4&8 \\ 5&0&6&7&3 \\ 9&6&0&2&10 \\ 4&7&2&0&11 \\ 8&3&10&11&0 \end{pmatrix}$ . The cable is to have the least possible total length.
Use Prim's algorithm, starting at $A$ , to find a minimum spanning tree. State the order in which the arcs are added and the total length.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).