User interface language: English | Español

Date November 2016 Marks available 4 Reference code 16N.3.AHL.TZ0.Hdm_4
Level Additional Higher Level Paper Paper 3 Time zone Time zone 0
Command term Hence, Find, and Draw Question number Hdm_4 Adapted from N/A

Question

The simple, complete graph κ n ( n > 2 ) has vertices A 1 ,   A 2 ,   A 3 ,   ,   A n . The weight of the edge from A i to A j is given by the number i + j .

Consider the general graph κ n .

(i)     Draw the graph κ 4  including the weights of all the edges.

(ii)     Use the nearest-neighbour algorithm, starting at vertex A 1 , to find a Hamiltonian cycle.

(iii)     Hence, find an upper bound to the travelling salesman problem for this weighted graph.

[4]
a.

Consider the graph κ 5 . Use the deleted vertex algorithm, with A 5 as the deleted vertex, to find a lower bound to the travelling salesman problem for this weighted graph.

[5]
b.

(i)     Use the nearest-neighbour algorithm, starting at vertex A 1 , to find a Hamiltonian cycle.

(ii)    Hence find and simplify an expression in n , for an upper bound to the travelling salesman problem for this weighted graph.

[7]
c.

By splitting the weight of the edge A i A j  into two parts or otherwise, show that all Hamiltonian cycles of κ n have the same total weight, equal to the answer found in (c)(ii).

[3]
d.

Markscheme

* This question is from an exam for a previous syllabus, and may contain minor differences in marking or structure.

(i)     N16/5/MATHL/HP3/ENG/TZ/DM/M/04.a     A1A1

 

Note: A1 for the graph, A1 for the weights.

 

(ii)     cycle is A 1 A 2 A 3 A 4 A 1      A1

(iii)     upper bound is 3 + 5 + 7 + 5 = 20      A1

[4 marks]

a.

with A 5  deleted, (applying Kruskal’s Algorithm) the minimum spanning tree will consist of the edges A 1 A 2 ,   A 1 A 3 A 1 A 4 , of weights 3, 4, 5     (M1)A1

the two edges of smallest weight from A 5 are A 5 A 1 and A 5 A 2 of weights 6 and 7     (M1)A1

so lower bound is 3 + 4 + 5 + 6 + 7 = 25      A1

[5 marks]

b.

(i)     starting at A 1 we go  A 2 ,   A 3     A n

we now have to take  A n A 1

thus the cycle is A 1 A 2 A 3 A n 1 A n A 1      A1A1

 

Note: Final A1 is for A n A 1 .

(ii)     smallest edge from A 1 is A 1 A 2 of weight 3, smallest edge from A 2 (to a new vertex) is A 2 A 3 of weight 5, smallest edge from A n 1 (to a new vertex) is A n 1 A n of weight 2 n 1      (M1)

weight of A n A 1 is  n + 1

weight is 3 + 5 + 7 + + ( 2 n 1 ) + ( n + 1 )      A1

= ( n 1 ) 2 ( 2 n + 2 ) + ( n + 1 )    M1A1

= n ( n + 1 ) (which is an upper bound)     A1

 

Note: Follow through is not applicable.

 

[7 marks]

c.

put a marker on each edge A i A j  so that i of the weight belongs to vertex A i  and j of the weight belongs to vertex A j      M1

the Hamiltonian cycle visits each vertex once and only once and for vertex A i  there will be weight i (belonging to vertex A i ) both going in and coming out     R1

so the total weight will be i = 1 n 2 i = 2 n 2 ( n + 1 ) = n ( n + 1 )      A1AG

 

Note: Accept other methods for example induction.

 

[3 marks]

d.

Examiners report

[N/A]
a.
[N/A]
b.
[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