User interface language: English | Español

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

Question

Let G be the graph below.

Find the total number of Hamiltonian cycles in G, starting at vertex A. Explain your answer.

[3]
a.

Find a minimum spanning tree for the subgraph obtained by deleting A from G.

[3]
b.i.

Hence, find a lower bound for the travelling salesman problem for G.

[3]
b.ii.

Give an upper bound for the travelling salesman problem for the graph above.

[2]
c.

Show that the lower bound you have obtained is not the best possible for the solution to the travelling salesman problem for G.

[3]
d.

Markscheme

Starting from vertex A there are 4 choices. From the next vertex there are three choices, etc…          M1R1

So the number of Hamiltonian cycles is 4! = 24.            A1  N1

[3 marks]

a.

Start (for instance) at B, using Prim′s algorithm Then D is the nearest vertex      M1

Next E is the nearest vertex       A1

Finally C is the nearest vertex So a minimum spanning tree is B → D → E → C           A1  N1

[3 marks]

b.i.

A lower bound for the travelling salesman problem is then obtained by adding the weights of AB and AE to the weight of the minimum      M1

spanning tree (ie 20)     A1

A lower bound is then 20 + 7 + 6 = 33          A1  N1

[3 marks]

b.ii.

ABCDE is an Hamiltonian cycle    A1

Thus an upper bound is given by 7 + 9 + 9 + 8 + 6 = 39    A1

[2 marks]

c.

Eliminating C from G a minimum spanning tree is E → A → B → D       M1

of weight 18     A1

Adding BC to CE(18 + 9 + 7) gives a lower bound of 34 > 33     A1

So 33 not the best lower bound.   AG  N0

[3 marks]

d.

Examiners report

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

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