| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | MST Method for Upper Bound |
| Difficulty | Moderate -0.8 This is a standard textbook application of the minimum spanning tree algorithm (likely Prim's or Kruskal's) followed by a routine shortcut improvement for the travelling salesman problem. The network is small (5 vertices), the MST construction is straightforward, and finding a shortcut requires minimal problem-solving insight—just identifying an obvious improvement to reduce the initial upper bound below 15 miles. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| A | B | C | D | E | |
| A | \(-\) | 4 | 7 | 8 | 2 |
| B | 4 | \(-\) | 1 | 5 | 6 |
| C | 7 | 1 | \(-\) | 2 | 7 |
| D | 8 | 5 | 2 | \(-\) | 3 |
| E | 2 | 6 | 7 | 3 | \(-\) |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | I | IL |
| J | JL | |
| K | KL |
Question 1:
1 | I | IL
J | JL
K | KLThis question should be answered on the sheet provided.
The table below shows the distances in miles between five villages. Jane lives in village A and is about to take her daughter's friends home to villages B, C, D and E. She will begin and end her journey at A and wishes to travel the minimum distance possible.
\begin{tabular}{c|ccccc}
& A & B & C & D & E \\
\hline
A & $-$ & 4 & 7 & 8 & 2 \\
B & 4 & $-$ & 1 & 5 & 6 \\
C & 7 & 1 & $-$ & 2 & 7 \\
D & 8 & 5 & 2 & $-$ & 3 \\
E & 2 & 6 & 7 & 3 & $-$ \\
\end{tabular}
\begin{enumerate}[label=(\alph*)]
\item Obtain a minimum spanning tree for the network and hence find an upper bound for the length of Jane's journey. [4 marks]
\item Using a shortcut, improve this upper bound to find an upper bound of less than 15 miles. [2 marks]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q1 [6]}}