Outline Kruskal's algorithm.

Sort edges in increasing weight; accept each unless it forms a cycle; stop at n-1 edges.

Why does Kruskal's algorithm reject an edge?

Its two ends are already connected, so it would form a cycle.

Outline Prim's algorithm.

Start at any vertex; repeatedly add the shortest edge joining the tree to a new vertex.

Can Prim's algorithm form a cycle?

No: it only ever adds an edge to a vertex not yet in the tree.

In matrix Prim's, what do you do with the start vertex's row?

Delete the row and number its column 1.

In matrix Prim's, what do you circle each time?

The smallest entry in the numbered columns, in a row not yet deleted.

What does a dash mean in a distance matrix?

There is no direct edge between those vertices.

What is special about the matrix of an undirected network?

It is symmetric about the leading diagonal.

Is the minimum spanning tree unique?

Yes if all the edge weights are different.

Does a minimum spanning tree give the shortest route between two vertices?

Not necessarily. It minimises total weight only.

If an edge in the tree is removed from the network, what do you do?

Re-find the tree: join the vertex by its cheapest remaining edge.

Minimum spanning treesEdexcel A-Level Further Maths: Flashcards

Card 1 of 130 of 13 known

Question

What is a minimum spanning tree?

Tap or press Space to reveal

Tap card or press Space to flip

See all 13 cards

What is a minimum spanning tree?: A spanning tree with the smallest possible total weight.
How many edges does a spanning tree of a network with $n$ vertices have?: $n-1$
Outline Kruskal's algorithm.: Sort edges in increasing weight; accept each unless it forms a cycle; stop at $n-1$ edges.
Why does Kruskal's algorithm reject an edge?: Its two ends are already connected, so it would form a cycle.
Outline Prim's algorithm.: Start at any vertex; repeatedly add the shortest edge joining the tree to a new vertex.
Can Prim's algorithm form a cycle?: No: it only ever adds an edge to a vertex not yet in the tree.
In matrix Prim's, what do you do with the start vertex's row?: Delete the row and number its column 1.
In matrix Prim's, what do you circle each time?: The smallest entry in the numbered columns, in a row not yet deleted.
What does a dash mean in a distance matrix?: There is no direct edge between those vertices.
What is special about the matrix of an undirected network?: It is symmetric about the leading diagonal.
Is the minimum spanning tree unique?: Yes if all the edge weights are different.
Does a minimum spanning tree give the shortest route between two vertices?: Not necessarily. It minimises total weight only.
If an edge in the tree is removed from the network, what do you do?: Re-find the tree: join the vertex by its cheapest remaining edge.

Exam questions on Minimum spanning trees

A network has six vertices $A$ , $B$ , $C$ , $D$ , $E$ and $F$ . Its edges and weights are $AB=7$ , $AC=4$ , $BC=6$ , $BD=9$ , $CD=5$ , $CE=8$ , $DE=3$ , $DF=12$ and $EF=10$ .
Explain why Kruskal's algorithm rejects the edge $AB$ .2 marks
Five towns $A$ , $B$ , $C$ , $D$ , $E$ are linked by roads. The distance matrix (in km) is given row by row, with columns in the order $A$ to $E$ and a dash meaning no direct road. Row $A$ : $-$ , $6$ , $9$ , $-$ , $-$ Row $B$ : $6$ , $-$ , $4$ , $8$ , $-$ Row $C$ : $9$ , $4$ , $-$ , $7$ , $5$ Row $D$ : $-$ , $8$ , $7$ , $-$ , $3$ Row $E$ : $-$ , $-$ , $5$ , $3$ , $-$
The road $DE$ is closed for repairs. Find the total length of the minimum spanning tree of the remaining roads.2 marks
A company must connect six villages $P$ , $Q$ , $R$ , $S$ , $T$ and $U$ with cable. The possible links and their costs, in thousands of pounds, are $PQ=14$ , $PR=9$ , $QR=11$ , $QS=8$ , $RS=12$ , $RT=10$ , $ST=6$ , $SU=13$ and $TU=7$ .
Use Kruskal's algorithm to find a minimum spanning tree, listing the edges in the order they are considered and stating which are accepted and which rejected.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).