| Date | None Specimen | Marks available | 8 | Reference code | SPNone.3dm.hl.TZ0.4 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Draw, Find, and Hence | Question number | 4 | Adapted from | N/A |
Question
The weights of the edges of a graph G with vertices A, B, C, D and E are given in the following table.
Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for G .
(i) Use Kruskal’s algorithm to find and draw a minimum spanning tree for the subgraph obtained by removing the vertex A from G .
(ii) Hence use the deleted vertex algorithm to find a lower bound for the travelling salesman problem for G .
Markscheme
using the nearest neighbour algorithm, starting with A,
\({\text{A}} \to {\text{E, E}} \to {\text{C}}\) A1
\({\text{C}} \to {\text{D, D}} \to {\text{B}}\) A1
\({\text{B}} \to {\text{A}}\) A1
the upper bound is therefore 9 + 10 + 16 + 13 + 11 = 59 A1
[4 marks]
(i) the edges are added in the order CE A1
BD A1
BE A1
A1
(ii) the weight of the minimum spanning tree is 37 (A1)
we now reconnect A with the 2 edges of least weight (M1)
i.e. AE and AB A1
the lower bound is therefore 37 + 9 + 11 = 57 A1
[8 marks]
