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.
The network below has six vertices, A to F. The number on each arc is its weight.
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.
State the weight of the minimum spanning tree.
4 marks
Show answer
a) DE add, AC add, BC add, CE add, AB reject, BD reject, DF addb) 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.
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.
State the total length of the minimum spanning tree.
4 marks
Show answer
a) GE, ED, DB, DC, CA, DFb) 70 m
3
The table shows the distances, in miles, between six villages in Shropshire, A to F.
A
B
C
D
E
F
A
−
23
31
18
27
35
B
23
−
16
29
21
30
C
31
16
−
25
14
22
D
18
29
25
−
26
33
E
27
21
14
26
−
19
F
35
30
22
33
19
−
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.
State the weight of the minimum spanning tree.
4 marks
Show answer
a) AD, AB, BC, CE, EFb) 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.
A
B
C
D
E
F
G
A
−
32
−
28
25
−
−
B
32
−
30
−
22
−
−
C
−
30
−
−
27
34
−
D
28
−
−
−
24
−
36
E
25
22
27
24
−
29
31
F
−
−
34
−
29
−
26
G
−
−
−
36
31
26
−
The seven towns are shown in the diagram. Draw the network of roads, labelling each arc with its length.
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.
State the total length of your minimum spanning tree.
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 26b) BE add, DE add, AE add, FG add, CE add, AD reject, EF addc) 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.
A
B
C
D
E
F
G
A
−
42
57
36
61
48
70
B
42
−
33
51
45
39
64
C
57
33
−
47
29
55
41
D
36
51
47
−
53
31
66
E
61
45
29
53
−
50
38
F
48
39
55
31
50
−
58
G
70
64
41
66
38
58
−
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.
Find the weight of the tree.
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 minutesc) 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.
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.
State the minimum cost.
Find the number of different minimum spanning trees for this network. Give a reason for your answer.
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) £26000c) 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.
Use Prim's algorithm, starting at C, to find a minimum spanning tree. State the order in which you select the arcs.
Kruskal's algorithm is applied to the same network. State the order in which the arcs are added to the tree.
State the total length of cable needed.
Explain why Kruskal's algorithm needs a check for cycles at every step but Prim's algorithm does not.
7 marks
Show answer
a) CD, DF, CB, BA, DE, EH, FGb) CD, DF, BC, EH, AB, DE, FGc) 127 md) 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
Given that x = 15, use Kruskal's algorithm to find a minimum spanning tree and state its weight.
Find the range of values of x for which arc BD is in every minimum spanning tree of the network.
For these values, write down the weight of the minimum spanning tree in terms of x
6 marks
Show answer
a) AC, CD, AB, DE, EF; weight 61b) 0 < x < 12c) 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.
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.
State the total length of track in the tree.
The landowner insists that the track QS must be resurfaced.
Find the minimum total length of track that links all seven checkpoints and includes QS, stating the arcs used.
7 marks
Show answer
a) ST add, PR add, QR add, SU add, PQ reject, TU reject, RS add, TV addb) 18.2 kmc) 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.
A
B
C
D
E
F
A
−
6.4
8.1
5.2
9.7
7.3
B
6.4
−
4.6
7.8
5.9
8.8
C
8.1
4.6
−
6.9
3.8
9.1
D
5.2
7.8
6.9
−
8.4
4.9
E
9.7
5.9
3.8
8.4
−
7.6
F
7.3
8.8
9.1
4.9
7.6
−
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.
Laying the cable costs £18 500 per km. Find the minimum cost of the network.
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 kmb) £460650c) 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.
A
B
C
D
E
F
G
A
−
18
25
31
22
37
29
B
18
−
14
27
30
33
24
C
25
14
−
16
28
26
35
D
31
27
16
−
19
21
34
E
22
30
28
19
−
32
17
F
37
33
26
21
32
−
23
G
29
24
35
34
17
23
−
Use Prim's algorithm, starting at A, to find a minimum spanning tree. State the order in which you select the arcs.
State the length of the minimum spanning tree.
A new sports hall, H, is built. Its distances, in metres, to the other blocks are
A
B
C
D
E
F
G
H
20
26
15
12
27
13
30
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, DFb) 105 mc) 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.
A
B
C
D
E
F
A
−
30
41
26
38
45
B
30
−
24
33
29
40
C
41
24
−
k
35
27
D
26
33
k
−
36
39
E
38
29
35
36
−
31
F
45
40
27
39
31
−
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.
Find the range of possible values of k
Write down, in terms of k, the weight of the minimum spanning tree.
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 < 30b) 106 + kc) 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.