| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Session | Specimen |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | State Best Bounds Interval |
| Difficulty | Moderate -0.5 This is a standard textbook TSP question testing routine application of lower bound algorithm (deleting vertices) and upper bound identification. Part (i) requires mechanical calculation of MST + reconnection edges. Parts (ii-iii) involve straightforward selection of best bounds from given data and systematic enumeration of a small number of routes. No novel insight required, just methodical application of taught algorithms. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Select edges: \(CD = 3\), \(DE = 4\), \(BC = 5\) (or \(CE = 7\)), \(AB = 9\), \(AD = 15\) | M1 | Attempt at minimum spanning tree |
| Correct minimum spanning tree identified with total weight | A1 | cao |
| Minimum spanning tree weight = \(3 + 4 + 5 + 9 + 15 = 36\) km | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Upper bound using nearest neighbour or doubling MST | M1 | Valid method stated |
| Upper bound = value stated | A1 | ft from their MST |
| Lower bound = \(36 + \) two shortest edges from deleted vertex | M1 | Valid lower bound method |
| Lower bound = value stated | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Attempt at nearest neighbour from different starting vertex | M1 | |
| Valid tour identified with working shown | A1 | |
| Best upper bound = stated value km | A1 | cao |
# Question 5:
## Part (i) - Minimum Spanning Tree / Prim's/Kruskal's Algorithm
| Answer | Mark | Guidance |
|--------|------|----------|
| Select edges: $CD = 3$, $DE = 4$, $BC = 5$ (or $CE = 7$), $AB = 9$, $AD = 15$ | M1 | Attempt at minimum spanning tree |
| Correct minimum spanning tree identified with total weight | A1 | cao |
| Minimum spanning tree weight = $3 + 4 + 5 + 9 + 15 = 36$ km | A1 | |
## Part (ii) - Upper and Lower Bounds
| Answer | Mark | Guidance |
|--------|------|----------|
| Upper bound using nearest neighbour or doubling MST | M1 | Valid method stated |
| Upper bound = value stated | A1 | ft from their MST |
| Lower bound = $36 + $ two shortest edges from deleted vertex | M1 | Valid lower bound method |
| Lower bound = value stated | A1 | cao |
## Part (iii) - Improved Upper Bound
| Answer | Mark | Guidance |
|--------|------|----------|
| Attempt at nearest neighbour from different starting vertex | M1 | |
| Valid tour identified with working shown | A1 | |
| Best upper bound = stated value km | A1 | cao |
---5 [Answer this question on the insert provided.]\\
\includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-3_659_1002_324_609}
In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the shortest distances in kilometres.\\
(i) The diagram on the insert shows the result of deleting vertex $F$ and all the arcs joined to $F$. Show that a lower bound for the length of the travelling salesperson problem on the original network is 38 km .
The corresponding lower bounds by deleting each of the other vertices are:
$$A : 40 \mathrm {~km} , \quad B : 39 \mathrm {~km} , \quad C : 35 \mathrm {~km} , \quad D : 37 \mathrm {~km} , \quad E : 35 \mathrm {~km} \text {. }$$
The route $A - B - C - D - E - F - A$ has length 47 km .\\
(ii) Using only this information, what are the best upper and lower bounds for the length of the solution to the travelling salesperson problem on the network?\\
(iii) By considering the orders in which vertices $C , D$ and $E$ can be visited, find the best upper bound given by a route of the form $A - B - \ldots - F - A$.
\hfill \mbox{\textit{OCR D1 Q5 [9]}}