| Date | May 2011 | Marks available | 1 | Reference code | 11M.3dm.hl.TZ0.2 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Find | Question number | 2 | Adapted from | N/A |
Question
The complete graph H has the following cost adjacency matrix.
Consider the travelling salesman problem for H .
By first finding a minimum spanning tree on the subgraph of H formed by deleting vertex A and all edges connected to A, find a lower bound for this problem.
Find the total weight of the cycle ADCBEA.
What do you conclude from your results?
Markscheme
using any method, the minimum spanning tree is (M1)
A2
Note: Accept MST = {BC, EC, DC} or {BC, EB, DC}
Note: In graph, line CE may be replaced by BE.
lower bound = weight of minimum spanning tree + 2 smallest weights connected to A (M1)
= 11 + 13 + 14 + 10 + 15 = 63 A1
[5 marks]
weight of ADCBEA = 10 + 14 + 11 + 13 + 15 = 63 A1
[1 mark]
the conclusion is that ADCBEA gives a solution to the travelling salesman problem A1
[1 mark]
Examiners report
This question was generally well answered although some candidates failed to realise the significance of the equality of the upper and lower bounds.
This question was generally well answered although some candidates failed to realise the significance of the equality of the upper and lower bounds.
This question was generally well answered although some candidates failed to realise the significance of the equality of the upper and lower bounds.
