| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2004 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | State Best Bounds Interval |
| Difficulty | Moderate -0.3 This is a standard textbook application of TSP algorithms (MST method, nearest neighbour, and deletion lower bound) with straightforward execution on a small 5-node network. The methods are algorithmic and well-practiced in D2, requiring careful arithmetic but no problem-solving insight or novel approaches. |
| Spec | 7.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 |
| \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | |
| \(A\) | \(-\) | 153 | 98 | 124 | 115 |
| \(B\) | 153 | \(-\) | 74 | 131 | 149 |
| \(C\) | 98 | 74 | \(-\) | 82 | 103 |
| \(D\) | 124 | 131 | 82 | \(-\) | 134 |
| \(E\) | 115 | 149 | 103 | 134 | \(-\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Minimum connector using Prim: AC, CB, CD, CE. Length = 98 + 74 + 82 + 103 = 357. So upper bound = 2 × 357 = 714 | M1 A1 [1, 3, 2, 4, 5], M1 A1 | 4 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(A (98) C (74) B (131) D (134) E (115) A\). Length = 98 + 74 + 131 + 134 + 115 = 552 | M1 A1, A1 | 3 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Residual minimum connector is AC, CB, CD. Length 254. Lower bound = 254 + 103 + 115 = 472 | M1, A1, M1 A1 | 4 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: 472 ≤ solution ≤ 552 | B1 ft | 1 mark |
### (a)(i)
**Answer:** Minimum connector using Prim: AC, CB, CD, CE. Length = 98 + 74 + 82 + 103 = 357. So upper bound = 2 × 357 = 714 | M1 A1 [1, 3, 2, 4, 5], M1 A1 | 4 marks
### (a)(ii)
**Answer:** $A (98) C (74) B (131) D (134) E (115) A$. Length = 98 + 74 + 131 + 134 + 115 = 552 | M1 A1, A1 | 3 marks
### (b)
**Answer:** Residual minimum connector is AC, CB, CD. Length 254. Lower bound = 254 + 103 + 115 = 472 | M1, A1, M1 A1 | 4 marks
### (c)
**Answer:** 472 ≤ solution ≤ 552 | B1 ft | 1 mark
---The table shows the least distances, in km, between five towns, $A$, $B$, $C$, $D$ and $E$.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
& $A$ & $B$ & $C$ & $D$ & $E$ \\
\hline
$A$ & $-$ & 153 & 98 & 124 & 115 \\
\hline
$B$ & 153 & $-$ & 74 & 131 & 149 \\
\hline
$C$ & 98 & 74 & $-$ & 82 & 103 \\
\hline
$D$ & 124 & 131 & 82 & $-$ & 134 \\
\hline
$E$ & 115 & 149 & 103 & 134 & $-$ \\
\hline
\end{tabular}
\end{center}
Nassim wishes to find an interval which contains the solution to the travelling salesman problem for this network.
\begin{enumerate}[label=(\alph*)]
\item Making your method clear, find an initial upper bound starting at $A$ and using
\begin{enumerate}[label=(\roman*)]
\item the minimum spanning tree method, [4]
\item the nearest neighbour algorithm. [3]
\end{enumerate}
\item By deleting $E$, find a lower bound. [4]
\item Using your answers to parts (a) and (b), state the smallest interval that Nassim could correctly write down. [1]
\end{enumerate}
(Total 12 marks)
\hfill \mbox{\textit{Edexcel D2 2004 Q3 [12]}}