What is the minimum spanning tree (minimum connector)?

The spanning tree with the smallest total weight.

State the steps of Kruskal's algorithm.

Sort arcs by increasing weight, then add each arc unless it forms a cycle, until n-1 arcs are chosen.

When do you reject an arc in Kruskal's algorithm?

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

State the steps of Prim's algorithm.

Start at any vertex, then repeatedly add the smallest arc joining the tree to a new vertex.

What is the main difference between Prim's and Kruskal's algorithms?

Prim's grows one connected tree from a start vertex; Kruskal's picks the smallest arcs anywhere, joining separate pieces.

Which algorithm needs no cycle check?

Prim's, because it only ever adds a new vertex.

How do you start Prim's algorithm on a matrix?

Label the starting vertex's column 1 and delete its row.

Why is a distance matrix symmetrical?

The arc XY has the same weight as YX, so each arc appears twice.

A matrix has 14 non-blank entries. How many arcs?

7, since each arc is entered twice.

Can a network have more than one MST?

Yes, if arcs have equal weights, but every MST has the same total weight.

Minimum spanning treesEdexcel International A Level 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 tree that includes every vertex of the network, using some of its arcs.
How many arcs does a spanning tree of $n$ vertices have?: $n-1$ .
What is the minimum spanning tree (minimum connector)?: The spanning tree with the smallest total weight.
State the steps of Kruskal's algorithm.: Sort arcs by increasing weight, then add each arc unless it forms a cycle, until $n-1$ arcs are chosen.
When do you reject an arc in Kruskal's algorithm?: When its two ends are already connected, so adding it would form a cycle.
State the steps of Prim's algorithm.: Start at any vertex, then repeatedly add the smallest arc joining the tree to a new vertex.
What is the main difference between Prim's and Kruskal's algorithms?: Prim's grows one connected tree from a start vertex; Kruskal's picks the smallest arcs anywhere, joining separate pieces.
Which algorithm needs no cycle check?: Prim's, because it only ever adds a new vertex.
How do you start Prim's algorithm on a matrix?: Label the starting vertex's column 1 and delete its row.
Why is a distance matrix symmetrical?: The arc $XY$ has the same weight as $YX$ , so each arc appears twice.
A matrix has 14 non-blank entries. How many arcs?: $7$ , since each arc is entered twice.
Can a network have more than one MST?: Yes, if arcs have equal weights, but every MST has the same total weight.

Exam questions on Minimum spanning trees

A network has five vertices $A$ , $B$ , $C$ , $D$ and $E$ . The arcs and their weights are $AB=7$ , $AC=4$ , $BC=6$ , $BD=3$ , $CD=8$ , $CE=5$ and $DE=9$ .
Use Kruskal's algorithm to find a minimum spanning tree for the network. List the arcs in the order in which you consider them, stating whether each is accepted or rejected, and find the total weight of the tree.2 marks
A network has five vertices $P$ , $Q$ , $R$ , $S$ and $T$ , shown by the following distance matrix. A dash means there is no arc. The rows, in order, are: $P$ : $-$ , 12, 9, 15, $-$ $Q$ : 12, $-$ , 8, $-$ , 14 $R$ : 9, 8, $-$ , 11, 10 $S$ : 15, $-$ , 11, $-$ , 6 $T$ : $-$ , 14, 10, 6, $-$ The columns are in the same order $P$ , $Q$ , $R$ , $S$ , $T$ .
Starting at $P$ , use Prim's algorithm to find a minimum spanning tree. State the order in which the arcs are added and the total weight of the tree.2 marks
A water company must connect six villages $A$ to $F$ with pipes. The possible pipes and their costs, in thousands of pounds, are $AB=12$ , $AC=9$ , $BC=7$ , $BD=15$ , $CD=11$ , $CE=14$ , $DE=6$ , $DF=10$ and $EF=8$ . Every village must be connected to every other village, directly or through other villages, at minimum total cost.
Use Kruskal's algorithm to find a minimum spanning tree, showing the order in which you consider the arcs, and state the minimum cost.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).