17N.3.AHL.TZ0.HDM_1

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

Mathilde delivers books to five libraries, A, B, C, D and E. She starts her deliveries at library D and travels to each of the other libraries once, before returning to library D. Mathilde wishes to keep her travelling distance to a minimum.

The weighted graph $H$ , representing the distances, measured in kilometres, between the five libraries, has the following table.

N17/5/MATHL/HP3/ENG/TZ0/DM/01

Draw the weighted graph $H$ .

[2]

Starting at library D use the nearest-neighbour algorithm, to find an upper bound for Mathilde’s minimum travelling distance. Indicate clearly the order in which the edges are selected.

[5]

By first removing library C, use the deleted vertex algorithm, to find a lower bound for Mathilde’s minimum travelling distance.

[4]

Markscheme / solution

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

N17/5/MATHL/HP3/ENG/TZ0/DM/M/01.a

complete graph on 5 vertices A1

weights correctly marked on graph A1

[2 marks]

clear indication that the nearest-neighbour algorithm has been applied M1

DA (or 16) A1

AB (or 18) then BC (or 15) A1

CE (or 17) then ED (or 19) A1

${\text{UB}} = 85$ A1

[5 marks]

an attempt to find the minimum spanning tree (M1)

DA (16) then BE (17) then AB (18) (total 51) A1

reconnect C with the two edges of least weight, namely CB (15) and CE (17) M1

${\text{LB}} = 83$ A1

[4 marks]

Examiners’ report

[N/A]