User interface language: English | Español

Date May Example question Marks available 2 Reference code EXM.2.AHL.TZ0.17
Level Additional Higher Level Paper Paper 2 Time zone Time zone 0
Command term Write down Question number 17 Adapted from N/A

Question

A canal system divides a city into six land masses connected by fifteen bridges, as shown in the diagram below.

State with reasons whether or not this graph has

Draw a graph to represent this map.

[2]
a.

Write down the adjacency matrix of the graph.

[2]
b.

List the degrees of each of the vertices.

[2]
c.

an Eulerian circuit.

[2]
d.i.

an Eulerian trail.

[2]
d.ii.

Find the number of walks of length 4 from E to F.

[2]
e.

Markscheme

    A2

[2 marks]

a.

M = A B C D E F A B C D E F ( 0 1 2 1 2 2 1 0 0 0 1 2 2 0 0 1 0 1 1 0 1 0 1 0 2 1 0 1 0 1 2 2 1 0 1 0 )      A2

Note: Award A1 for one error or omission, A0 for more than one error or omission. Two symmetrical errors count as one error.

[2 marks]

b.

A   B   C   D   E   F

(8, 4   4, 3  5, 6)    A2

Note: Award no more than A1 for one error, A0 for more than one error.

[2 marks]

c.

no, because there are odd vertices   M1A1

[2 marks]

d.i.

yes, because there are exactly two odd vertices       M1A1

[2 marks]

d.ii.

M4 = A B C D E F A B C D E F ( 309 174 140 118 170 214 174 117 106 70 122 132 140 106 117 66 134 138 118 70 66 53 80 102 170 122 134 80 157 170 214 132 138 102 170 213 )      (M1)A1

number of walks of length 4 is 170

Note: The complete matrix need not be shown. Only one of the FE has to be shown.

[2 marks]

e.

Examiners report

[N/A]
a.
[N/A]
b.
[N/A]
c.
[N/A]
d.i.
[N/A]
d.ii.
[N/A]
e.

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