User interface language: English | Español

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

Question

The adjacency matrix of the graph G, with vertices P, Q, R, S, T is given by:

P Q R S T P Q R S T ( 0 2 1 1 0 2 1 1 1 0 1 1 1 0 2 1 1 0 0 0 0 0 2 0 0 )

Draw the graph of G.

[3]
a.

Define an Eulerian circuit.

[1]
b.i.

Write down an Eulerian circuit in G starting at P.

[2]
b.ii.

Define a Hamiltonian cycle.

[2]
c.i.

Explain why it is not possible to have a Hamiltonian cycle in G.

[3]
c.ii.

Find the number of walks of length 5 from P to Q.

[4]
d.i.

Which pairs of distinct vertices have more than 15 walks of length 3 between them?

[4]
d.ii.

Markscheme

   A3

 

Note: Award A2 for one missing or misplaced edge,            

          A1 for two missing or misplaced edges.

[3 marks]

a.

an Eulerian circuit is one that contains every edge of the graph exactly once    A1

[1 mark]

b.i.

a possible Eulerian circuit is

P → Q → S → P → Q → Q → R → T → R → R → P       A2

[2 marks]

b.ii.

a Hamiltonian cycle passes through each vertex of the graph      A1

exactly once      A1

[2 marks]

c.i.

to pass through T, you must have come from R and must return to R.     R3

hence there is no Hamiltonian cycle

[3 marks]

c.ii.

using the adjacency matrix A ( 0 2 1 1 0 2 1 1 1 0 1 1 1 0 2 1 1 0 0 0 0 0 2 0 0 ) ,      (M1)

we need the entry in the first row second column of the matrix A5     (M1)

A5  =  ( 245 309 274 143 126 309 363 322 168 156 274 322 295 141 164 143 168 141 77 72 126 156 164 72 72 )      (A1)

hence there are 309 ways      A1

[4 marks]

d.i.

A3 = ( 13 21 17 10 6 21 22 19 11 8 17 19 18 7 14 10 11 7 5 4 6 8 14 4 4 )       (M1)

hence the pairs of vertices are PQ, PR and QR     A1A1A1

[4 marks]

d.ii.

Examiners report

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

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