EXM.1.AHL.TZ0.1

pestleMathematicsAIHLPaper 1EXM· ahl-3-16-tree-and-cycle-algorithms-chinese-postman-travelling-salesmansource ↗

The cost adjacency matrix below represents the distance in kilometres, along routes between bus stations.

All the values in the matrix are positive, distinct integers.

It is decided to electrify some of the routes, so that it will be possible to travel from any station to any other station solely on electrified routes. In order to achieve this with a minimal total length of electrified routes, Prim’s algorithm for a minimal spanning tree is used, starting at vertex A.

The algorithm adds the edges in the following order:

AB AC CD DE.

There is only one minimal spanning tree.

Find with a reason, the value of $x$ .

[2]

If the total length of the minimal spanning tree is 14, find the value of $s$ .

[2]

Hence, state, with a reason, what can be deduced about the values of $p$ , $q$ , $r$ .

[2]

Markscheme / solution

AB must be the length of the smallest edge from A so $x = 1$ . R1A1

[2 marks]

$1 + 2 + 3 + s = 14 \Rightarrow s = 8$ M1A1

[2 marks]

The last minimal edge chosen must connect to E , so since $s = 8$ each of $p$ , $q$ , $r$ must be ≥ 9. R1A1

[2 marks]

Examiners’ report

[N/A]