17M.3.AHL.TZ0.HDM_2

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

The weights of the edges in the complete graph $G$ are given in the following table.

M17/5/MATHL/HP3/ENG/TZ0/DM/02

Starting at A , use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for $G$ .

[5]

By first deleting vertex A , use the deleted vertex algorithm together with Kruskal’s algorithm to find a lower bound for the travelling salesman problem for $G$ .

[7]

Markscheme / solution

* This question is from an exam for a previous syllabus, and may contain minor differences in marking or structure.

the edges are traversed in the following order

AB A1

CF A1

ED A1

DA A1

${\text{upper bound}} = {\text{weight of this cycle}} = 4 + 1 + 2 + 7 + 11 + 8 = 33$ A1

[5 marks]

having deleted A, the order in which the edges are added is

BC A1

CF A1

CD A1

EF A1

Note: Accept indication of the correct order on a diagram.

to find the lower bound, we now reconnect A using the two edges with the lowest weights, that is AB and AF (M1)(A1)

${\text{lower bound}} = 1 + 2 + 5 + 7 + 4 + 6 = 25$ A1

Note: Award (M1)(A1)A1 for ${\text{LB}} = 15 + 4 + 6 = 25$ obtained either from an incorrect order of correct edges or where order is not indicated.

[7 marks]

Examiners’ report

[N/A]