| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Complete Table by Inspection |
| Difficulty | Moderate -0.8 This is a routine application of the nearest neighbour algorithm to a small network (5 vertices). Students must complete a distance table by inspection from a diagram, then mechanically apply a standard algorithm. The question requires careful bookkeeping but no problem-solving insight or novel reasoning—it's a textbook exercise testing procedural fluency in a D2 topic. |
| Spec | 7.02p Networks: weighted graphs, modelling connections7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Complete network with 5 nodes, all shortest distances correctly shown: \(AB=5, AC=9, AD=16, AE=18, BC=8, BD=13, BE=11, CD=10, CE=12, DE=7\) | M1 | Method to find shortest distances |
| All values correct | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(A \to B\) (nearest unvisited, 5), \(B \to C\) (8), \(C \to D\) (10), \(D \to E\) (7), \(E \to A\) (18); Tour length \(= 5+8+10+7+18 = 48\) | M1 | Correct application of nearest neighbour from \(A\) |
| 48 miles | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route interpreted using original network, e.g. \(A \to B \to C \to D \to E \to C \to A\) or similar valid interpretation showing actual roads used | M1 | Correct interpretation attempt |
| Fully correct route stated | A1 |
# Question 1:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Complete network with 5 nodes, all shortest distances correctly shown: $AB=5, AC=9, AD=16, AE=18, BC=8, BD=13, BE=11, CD=10, CE=12, DE=7$ | M1 | Method to find shortest distances |
| All values correct | A1 | |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A \to B$ (nearest unvisited, 5), $B \to C$ (8), $C \to D$ (10), $D \to E$ (7), $E \to A$ (18); Tour length $= 5+8+10+7+18 = 48$ | M1 | Correct application of nearest neighbour from $A$ |
| 48 miles | A1 | |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route interpreted using original network, e.g. $A \to B \to C \to D \to E \to C \to A$ or similar valid interpretation showing actual roads used | M1 | Correct interpretation attempt |
| Fully correct route stated | A1 | |
---\begin{enumerate}
\item This question should be answered on the sheet provided.
\end{enumerate}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e892e87c-1c2d-4f97-ac23-41e38663d0f0-02_485_995_285_477}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
The network in Figure 1 shows the distances, in miles, between the five villages in which Sarah is planning to enquire about holiday work, with village $A$ being Sarah's home village.\\
(a) Illustrate this situation as a complete network showing the shortest distances.\\
(2 marks)\\
(b) Use the nearest neighbour algorithm, starting with $A$, to find an upper bound to the length of a tour beginning and ending at $A$.\\
(2 marks)\\
(c) Interpret the tour found in part (b) in terms of the original network.\\
(2 marks)\\
\hfill \mbox{\textit{Edexcel D2 Q1 [6]}}