User interface language: English | Español

Date May 2021 Marks available 1 Reference code 21M.1.AHL.TZ1.10
Level Additional Higher Level Paper Paper 1 Time zone Time zone 1
Command term Describe Question number 10 Adapted from N/A

Question

An engineer plans to visit six oil rigs (AF) in the Gulf of Mexico, starting and finishing at A. The travelling time, in minutes, between each of the rigs is shown in the table.

The data above can be represented by a graph G.

Use Prim’s algorithm to find the weight of the minimum spanning tree of the subgraph of G obtained by deleting A and starting at B. List the order in which the edges are selected.

[4]
a.i.

Hence find a lower bound for the travelling time needed to visit all the oil rigs.

[2]
a.ii.

Describe how an improved lower bound might be found.

[1]
b.

Markscheme

use of Prim’s algorithm                    M1

BC    46                A1

BD    58                A1

DE    23

EF    47

Total  174               A1


Note: Award M0A0A0A1 for 174 without correct working e.g. use of Kruskal’s, or with no working.
Award M1A0A0A1 for 174 by using Prim’s from an incorrect starting point.


[4 marks]

a.i.

AB+AC=55+63=118                (M1)

174+118=292 minutes                   A1 


[2 marks]

a.ii.

delete a different vertex                  A1 


[1 mark]

b.

Examiners report

[N/A]
a.i.
[N/A]
a.ii.
[N/A]
b.

Syllabus sections

Topic 3—Geometry and trigonometry » AHL 3.16—Tree and cycle algorithms, Chinese postman, travelling salesman
Show 87 related questions
Topic 3—Geometry and trigonometry

View options