19N.3.AHL.TZ0.HDM_1

pestleMathematicsAIHLPaper 319N· ahl-3-16-tree-and-cycle-algorithms-chinese-postman-travelling-salesmansource ↗

A driver needs to make deliveries to five shops $A$ , $B$ , $C$ , $D$ and $E$ . The driver starts and finishes his journey at the warehouse $W$ . The driver wants to find the shortest route to visit all the shops and return to the warehouse. The distances, in kilometres, between the locations are given in the following table.

By deleting $W$ , use the deleted vertex algorithm to find a lower bound for the length of a route that visits every shop, starting and finishing at $W$ .

[6]

Starting from $W$ , use the nearest-neighbour algorithm to find a route which gives an upper bound for this problem and calculate its length.

[4]

Markscheme / solution

deleting ${\text{W}}$ and its adjacent edges, the minimal spanning tree is

A1A1A1A1

Note: Award the A1’s for either the edges or their weights.

the minimum spanning tree has weight = 54

Note: Accept a correct drawing of the minimal spanning tree.

adding in the weights of 2 deleted edges of least weight ${\text{WB}}$ and ${\text{WC}}$ (M1)
lower bound = 54 + 36 + 39

= 129 A1

[6 marks]

attempt at the nearest-neighbour algorithm M1

${\text{WB}}$
${\text{BA}}$
${\text{AD}}$
${\text{DE}}$
${\text{EC}}$
${\text{CW}}$ A1

Note: Award M1 for a route that begins with ${\text{WB}}$ and then ${\text{BA}}$ .

upper bound = 36 + 11 + 15 + 12 + 22 + 39 = 135 (M1)A1

[4 marks]

Examiners’ report

[N/A]