| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2008 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | State Best Bounds Interval |
| Difficulty | Standard +0.3 This is a standard D2 travelling salesman problem following a predictable algorithm-based structure. Students apply Kruskal's algorithm, calculate upper bounds via MST doubling and shortcuts, apply nearest neighbour, and find lower bounds by deletion—all routine procedures covered extensively in the specification with minimal problem-solving required beyond careful execution. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| Answer | Marks | Guidance |
|---|---|---|
| (a) GH(38) GF(56) CA(57) EC(59) FE(61) CD(64) CB(68) | M1A1ft | 2 |
| (b) \(2 \times 403 = 806\) (km) | B1 | 1 |
| (c) e.g. DH saves 167; AB saves 23; \(806 - 190 = 616\) (km) | M1A1, A1 |
| Answer | Marks | Guidance |
|---|---|---|
| \[68 + 57 + 98 + 61 + 56 + 38 + 111 + 108 = 597 \text{ (km)}\] | M1A1, A1 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| M1A1M1A1ft | 4 | |
| (f) RMST weight \(= 444\); Lower bound \(= 444 + 59 + 57 = 560\) (km); \(560 < \text{length} \leq 597\) | B2,1,0 | 2 |
**(a)** GH(38) GF(56) CA(57) EC(59) FE(61) CD(64) CB(68) | M1A1ft | 2 |
**(b)** $2 \times 403 = 806$ (km) | B1 | 1 |
**(c)** e.g. DH saves 167; AB saves 23; $806 - 190 = 616$ (km) | M1A1, A1 | |
**(d)** eg A B C E F G H D C A
$$\text{B} \quad \text{C} \quad \text{A} \quad \text{E} \quad \text{F} \quad \text{G} \quad \text{H} \quad \text{D} \quad \text{B}$$
$$68 + 57 + 98 + 61 + 56 + 38 + 111 + 108 = 597 \text{ (km)}$$ | M1A1, A1 | 3 |
**(e)** Delete C
[Diagram showing modified network with E-F-D triangle structure]
| M1A1M1A1ft | 4 |
**(f)** RMST weight $= 444$; Lower bound $= 444 + 59 + 57 = 560$ (km); $560 < \text{length} \leq 597$ | B2,1,0 | 2 |
[16]7.\\
\includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-3_738_1052_466_516}
The network in the diagram above shows the distances, in km, between eight weather data collection points. Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum distance.
\begin{enumerate}[label=(\alph*)]
\item Obtain a minimum spanning tree for the network using Kruskal's algorithm, stating the order in which you select the arcs.
\item Use your answer to part (a) to determine an initial upper bound for the length of the route.
\item Starting from your initial upper bound use short cuts to find an upper bound, which is below 630 km . State the corresponding route.
\item Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route.
\item By deleting C, and all of its arcs, find a lower bound for the length of the route.
\item Use your results to write down the smallest interval which you are confident contains the optimal length of the route.\\
(2) (Total 16 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2008 Q7 [16]}}