User interface language: English | Español

Date May 2018 Marks available 1 Reference code 18M.3.AHL.TZ0.Hdm_1
Level Additional Higher Level Paper Paper 3 Time zone Time zone 0
Command term State Question number Hdm_1 Adapted from N/A

Question

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]
b.

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

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]

b.

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]
b.
[N/A]
c.ii.
[N/A]
c.iii.

Syllabus sections

Topic 3—Geometry and trigonometry » AHL 3.16—Tree and cycle algorithms, Chinese postman, travelling salesman
Show 87 related questions
Topic 3—Geometry and trigonometry

View options