21M.1.AHL.TZ1.10

pestleMathematicsAIHLPaper 121M· ahl-3-16-tree-and-cycle-algorithms-chinese-postman-travelling-salesmansource ↗

An engineer plans to visit six oil rigs $(A - F)$ 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]

Markscheme / solution

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]

Examiners’ report

[N/A]

a.i.

[N/A]

a.ii.

[N/A]