18M.3.AHL.TZ0.HDM_1

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

Consider the following weighted graph G.

State what feature of G ensures that G has an Eulerian trail.

[1]

a.i.

State what feature of G ensures that G does not have an Eulerian circuit.

[1]

a.ii.

Write down an Eulerian trail in G.

[2]

Starting and finishing at B, find a solution to the Chinese postman problem for G.

[3]

c.ii.

Calculate the total weight of the solution.

[1]

c.iii.

Markscheme / solution

G has an Eulerian trail because it has (exactly) two vertices (B and F) of odd degree R1

[1 mark]

a.i.

G does not have an Eulerian circuit because not all vertices are of even degree R1

[1 mark]

a.ii.

for example BAEBCEFCDF A1A1

Note: Award A1 for start/finish at B/F, A1 for the middle vertices.

[2 marks]

we require the Eulerian trail in (b), (weight = 65) (M1)

and the minimum walk FEB (15) A1

for example BAEBCEFCDFEB A1

Note: Accept EB added to the end or FE added to the start of their answer in (b) in particular for follow through.

[3 marks]

c.ii.

total weight is (65 + 15=)80 A1

[1 mark]

c.iii.

Examiners’ report

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

c.ii.

[N/A]

c.iii.