EXN.1.AHL.TZ0.11

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

Nymphenburg Palace in Munich has extensive grounds with $9$ points of interest (stations) within them.

These nine points, along with the palace, are shown as the vertices in the graph below. The weights on the edges are the walking times in minutes between each of the stations and the total of all the weights is $105$ minutes.

Anders decides he would like to walk along all the paths shown beginning and ending at the Palace (vertex A).

Use the Chinese Postman algorithm, clearly showing all the stages, to find the shortest time to walk along all the paths.

Markscheme / solution

* This sample question was produced by experienced DP mathematics senior examiners to aid teachers in preparing for external assessment in the new MAA course. There may be minor differences in formatting compared to formal exam papers.

Odd vertices are B, F, H and I (M1)A1

Pairing the vertices M1

BF and HI    $9 + 3 = 12$
BH and FI    $4 + 11 = 15$
BI and FH    $3 + 8 = 11$ A2

Note: award A1 for two correct totals.

Shortest time is $105 + 11 = 116$ (minutes) M1A1

[7 marks]

Examiners’ report

[N/A]