| Date | May 2018 | Marks available | 1 | Reference code | 18M.3dm.hl.TZ0.1 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | State | Question number | 1 | Adapted from | N/A |
Question
Consider the following weighted graph G.
State what feature of G ensures that G has an Eulerian trail.
State what feature of G ensures that G does not have an Eulerian circuit.
Write down an Eulerian trail in G.
State the Chinese postman problem.
Starting and finishing at B, find a solution to the Chinese postman problem for G.
Calculate the total weight of the solution.
Markscheme
G has an Eulerian trail because it has (exactly) two vertices (B and F) of odd degree R1
[1 mark]
G does not have an Eulerian circuit because not all vertices are of even degree R1
[1 mark]
for example BAEBCEFCDF A1A1
Note: Award A1 for start/finish at B/F, A1 for the middle vertices.
[2 marks]
to determine the shortest route (walk) around a weighted graph A1
using each edge (at least once, returning to the starting vertex) A1
Note: Correct terminology must be seen. Do not accept trail, path, cycle or circuit.
[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]
total weight is (65 + 15=)80 A1
[1 mark]
