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 = ABCDEFABCDEF(012122100012200101101010210101221010)ABCDEFABCDEF⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜012122100012200101101010210101221010⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟     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 = ABCDEFABCDEF(30917414011817021417411710670122132140106117661341381187066538010217012213480157170214132138102170213)ABCDEFABCDEF⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜30917414011817021417411710670122132140106117661341381187066538010217012213480157170214132138102170213⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟     (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