Robinson Tuition
AS Decision Mathematics 1 · Edexcel 8FM0 · free Further Maths worksheet

Minimum spanning trees

Kruskal's algorithm with the order edges are chosen or rejected, Prim's algorithm on a network and on a distance matrix with the order vertices are added, weight of the tree, problems in context.

12 original questions, 71 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.

Worksheet PDFWorked solutions PDFAnswers PDF

The questions

1

The network below has six vertices, A to F. The number on each arc is its weight.

  1. Use Kruskal's algorithm to find a minimum spanning tree for the network. List the arcs in the order that you consider them and state whether each arc is added to the tree.
  2. State the weight of the minimum spanning tree.
856971141012ABCDEFDiagram NOT accurately drawn
4 marks
Show answer
a) DE add, AC add, BC add, CE add, AB reject, BD reject, DF add b) 32
2

The network below shows the lengths, in metres, of paths between seven huts, A to G, at a scout camp in the Lake District.

  1. Use Prim's algorithm, starting at G, to find a minimum spanning tree for the network. State the order in which you select the arcs.
  2. State the total length of the minimum spanning tree.
14111691218101520131721ABCDEFGDiagram NOT accurately drawn
4 marks
Show answer
a) GE, ED, DB, DC, CA, DF b) 70 m
3

The table shows the distances, in miles, between six villages in Shropshire, A to F.

ABCDEF
A−2331182735
B23−16292130
C3116−251422
D182925−2633
E27211426−19
F3530223319−
  1. Use Prim's algorithm, starting at A, to find a minimum spanning tree for the six villages. You must state the order in which you select the arcs.
  2. State the weight of the minimum spanning tree.
4 marks
Show answer
a) AD, AB, BC, CE, EF b) 90 miles
4

The table shows the lengths, in km, of the roads between seven towns, A to G, in Lincolnshire. A dash means there is no direct road.

ABCDEFG
A−32−2825−−
B32−30−22−−
C−30−−2734−
D28−−−24−36
E25222724−2931
F−−34−29−26
G−−−363126−
  1. The seven towns are shown in the diagram. Draw the network of roads, labelling each arc with its length.
  2. Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order that you consider them and state whether each is added.
  3. State the total length of your minimum spanning tree.
ABCDEFGDiagram NOT accurately drawn
6 marks
Show answer
a) Network drawn with arcs AB 32, AD 28, AE 25, BC 30, BE 22, CE 27, CF 34, DE 24, DG 36, EF 29, EG 31, FG 26 b) BE add, DE add, AE add, FG add, CE add, AD reject, EF add c) 153 km
5

The table shows the times, in minutes, to drive between seven depots, A to G, of a delivery firm in the West Midlands.

ABCDEFG
A−425736614870
B42−3351453964
C5733−47295541
D365147−533166
E61452953−5038
F4839553150−58
G706441663858−
  1. Use Prim's algorithm, starting at D, to find a minimum spanning tree. State the order in which you add the vertices to the tree.
  2. Find the weight of the tree.
  3. Kruskal's algorithm is also applied to the same table. Explain whether Kruskal's algorithm could give a different minimum spanning tree.
6 marks
Show answer
a) D, F, A, B, C, E, G (arcs DF, DA, FB, BC, CE, EG) b) 206 minutes c) No: every weight is different, so there is only one minimum spanning tree. Kruskal adds the same arcs, possibly in a different order.
6

The network below shows the costs, in thousands of pounds, of laying water pipes between six farms, A to F, in Devon.

  1. Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order that you consider them and state whether each is added.
  2. State the minimum cost.
  3. Find the number of different minimum spanning trees for this network. Give a reason for your answer.
654768569ABCDEFDiagram NOT accurately drawn
5 marks
Show answer
a) AD add, BC add, CF add, AB add, BE add (AB, BE, DE in any order: the third of these is rejected) b) £26000 c) 3
7

The network below shows the lengths, in metres, of cable needed to link eight buildings, A to H, on a university campus in Leeds.

  1. Use Prim's algorithm, starting at C, to find a minimum spanning tree. State the order in which you select the arcs.
  2. Kruskal's algorithm is applied to the same network. State the order in which the arcs are added to the tree.
  3. State the total length of cable needed.
  4. Explain why Kruskal's algorithm needs a check for cycles at every step but Prim's algorithm does not.
1923172115262418201627252228ABCDEFGHDiagram NOT accurately drawn
7 marks
Show answer
a) CD, DF, CB, BA, DE, EH, FG b) CD, DF, BC, EH, AB, DE, FG c) 127 m d) Prim always joins a vertex not yet in the tree, so it can never close a cycle; Kruskal takes arcs in order of size anywhere in the network, so an arc may join two vertices that are already connected.
8

The network below has six vertices. The weight of arc BD is x, where x > 0

  1. Given that x = 15, use Kruskal's algorithm to find a minimum spanning tree and state its weight.
  2. Find the range of values of x for which arc BD is in every minimum spanning tree of the network.
  3. For these values, write down the weight of the minimum spanning tree in terms of x
12914112013182216xABCDEFDiagram NOT accurately drawn
6 marks
Show answer
a) AC, CD, AB, DE, EF; weight 61 b) 0 < x < 12 c) 49 + x
9

A cycle club in Cornwall wants to resurface tracks so that seven checkpoints, P to V, are all linked. The network shows the lengths, in km, of the possible tracks.

  1. Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order that you consider them and state whether each is added.
  2. State the total length of track in the tree.

The landowner insists that the track QS must be resurfaced.

  1. Find the minimum total length of track that links all seven checkpoints and includes QS, stating the arcs used.
3.22.62.94.13.55.42.43.04.83.33.84.4PQRSTUVDiagram NOT accurately drawn
7 marks
Show answer
a) ST add, PR add, QR add, SU add, PQ reject, TU reject, RS add, TV add b) 18.2 km c) QS, ST, PR, QR, SU, TV; 18.8 km
10

A broadband company plans to link six villages in Leicestershire with fibre cable laid along roads: Ashby (A), Brill (B), Cotes (C), Dunton (D), Elm (E) and Foxley (F). The table shows the road distances, in km, between the villages.

ABCDEF
A−6.48.15.29.77.3
B6.4−4.67.85.98.8
C8.14.6−6.93.89.1
D5.27.86.9−8.44.9
E9.75.93.88.4−7.6
F7.38.89.14.97.6−
  1. Use Prim's algorithm, starting at Ashby, to find the minimum length of cable needed to link all six villages. You must state the order in which you select the arcs.
  2. Laying the cable costs £18 500 per km. Find the minimum cost of the network.
  3. Give one practical reason why the company might not use the network found in part (a).
7 marks
Show answer
a) AD, DF, AB, BC, CE; 24.9 km b) £460650 c) For example: a tree has no spare links, so one broken cable cuts off every village beyond it; or some roads may be hard to dig up.
11

The table shows the distances, in metres, between seven classroom blocks, A to G, in a large secondary school in Bristol. The school wants to link every block with a covered walkway of minimum total length.

ABCDEFG
A−182531223729
B18−1427303324
C2514−16282635
D312716−192134
E22302819−3217
F3733262132−23
G292435341723−
  1. Use Prim's algorithm, starting at A, to find a minimum spanning tree. State the order in which you select the arcs.
  2. State the length of the minimum spanning tree.

A new sports hall, H, is built. Its distances, in metres, to the other blocks are

ABCDEFG
H20261512271330
  1. Find a minimum spanning tree for all eight buildings, explaining your method, and state its length.
8 marks
Show answer
a) AB, BC, CD, DE, EG, DF b) 105 m c) DH, FH, BC, CH, EG, AB, DE; 108 m
12

The table shows the distances, in km, between six petrol stations, A to F, on a motorway network. The distance from C to D is k km.

ABCDEF
A−3041263845
B30−24332940
C4124−k3527
D2633k−3639
E38293536−31
F4540273931−

Prim's algorithm, starting at A, is applied to the table. The vertices are added to the tree in the order A, D, C, B, F, E.

  1. Find the range of possible values of k
  2. Write down, in terms of k, the weight of the minimum spanning tree.
  3. Given instead that k = 34, find the order in which the vertices are added and the weight of the minimum spanning tree.
7 marks
Show answer
a) 0 < k < 30 b) 106 + k c) A, D, B, C, F, E; 136 km

Your score

Answer the questions above and your score appears here.

Every question here is original and written by Robinson Tuition. It follows the Edexcel AS Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.

All AS Decision Mathematics 1 topics