| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Apply Prim's Algorithm |
| Difficulty | Moderate -0.3 This is a standard D2 question applying Prim's algorithm and TSP bounds using textbook methods. Part (a) is routine MST construction, parts (b-d) apply standard shortcuts and deletion techniques with clear instructions. The table lookup and arithmetic are straightforward, requiring no novel insight—slightly easier than average A-level maths. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| Leeds | Liverpool | Manchester | Newcastle | Nottingham | Oxford | York | |
| Leeds | - | 71 | 40 | 96 | 71 | 165 | 28 |
| Liverpool | 71 | - | 31 | 155 | 92 | 155 | 93 |
| Manchester | 40 | 31 | - | 136 | 62 | 141 | 67 |
| Newcastle | 96 | 155 | 136 | - | 156 | 250 | 78 |
| Nottingham | 71 | 92 | 62 | 156 | - | 94 | 78 |
| Oxford | 165 | 155 | 141 | 250 | 94 | - | 172 |
| York | 28 | 93 | 67 | 78 | 78 | 172 | - |
6. This question should be answered on the sheet provided.
A furniture company in Leeds is considering opening outlets in six other cities.\\
The table below shows the distances, in miles, between all seven cities.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& Leeds & Liverpool & Manchester & Newcastle & Nottingham & Oxford & York \\
\hline
Leeds & - & 71 & 40 & 96 & 71 & 165 & 28 \\
\hline
Liverpool & 71 & - & 31 & 155 & 92 & 155 & 93 \\
\hline
Manchester & 40 & 31 & - & 136 & 62 & 141 & 67 \\
\hline
Newcastle & 96 & 155 & 136 & - & 156 & 250 & 78 \\
\hline
Nottingham & 71 & 92 & 62 & 156 & - & 94 & 78 \\
\hline
Oxford & 165 & 155 & 141 & 250 & 94 & - & 172 \\
\hline
York & 28 & 93 & 67 & 78 & 78 & 172 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Starting with Leeds, obtain and draw a minimum spanning tree for this network of cities showing your method clearly.\\
(4 marks)\\
A representative of the company is to visit each of the areas being considered. He wishes to plan a journey of minimum length starting and ending in Leeds and visiting each of the other cities in the table once.
Assuming that the network satisfies the triangle inequality,
\item find an initial upper bound for the length of his journey,
\item improve this upper bound to find an upper bound of less than 575 miles.
\item By deleting Leeds, find a lower bound for his journey.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q6 [14]}}