EXM.2.AHL.TZ0.19
Let G be the graph below.
Find the total number of Hamiltonian cycles in G, starting at vertex A. Explain your answer.
Find a minimum spanning tree for the subgraph obtained by deleting A from G.
Hence, find a lower bound for the travelling salesman problem for G.
Give an upper bound for the travelling salesman problem for the graph above.
Show that the lower bound you have obtained is not the best possible for the solution to the travelling salesman problem for G.
Markscheme / solution
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]
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]
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]
ABCDE is an Hamiltonian cycle A1
Thus an upper bound is given by 7 + 9 + 9 + 8 + 6 = 39 A1
[2 marks]
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]