| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | MST Method for Upper Bound |
| Difficulty | Moderate -0.3 This is a standard algorithmic application question from D2. Students must execute two well-defined algorithms (nearest neighbour and MST deletion method) with clear procedures. While the 8-vertex table requires careful bookkeeping and arithmetic, no problem-solving insight is needed—just methodical application of learned algorithms. The mark allocation (11 marks) reflects the computational work rather than conceptual difficulty. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| A | B | \(C\) | D | \(E\) | \(F\) | G | \(H\) | |
| A | - | 85 | 59 | 31 | 47 | 52 | 74 | 41 |
| B | 85 | - | 104 | 73 | 51 | 68 | 43 | 55 |
| C | 59 | 104 | - | 54 | 62 | 88 | 61 | 45 |
| D | 31 | 73 | 54 | - | 40 | 59 | 65 | 78 |
| E | 47 | 51 | 62 | 40 | - | 56 | 71 | 68 |
| \(F\) | 52 | 68 | 88 | 59 | 56 | - | 53 | 49 |
| G | 74 | 43 | 61 | 65 | 71 | 53 | - | 63 |
| H | 41 | 55 | 45 | 78 | 68 | 49 | 63 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(A \to D\) (31), \(D \to E\) (40), \(E \to B\) (51), \(B \to G\) (43), \(G \to F\) (53), \(F \to H\) (49), \(H \to C\) (45), \(C \to A\) (59) | M1 A1 | M1 for correct method, A1 correct sequence |
| Total \(= 31+40+51+43+53+49+45+59 = 371\) | A1 | Upper bound = 371 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Starting from any node, applying Prim's to \(\{A,B,C,D,E,F,G\}\) | M1 | |
| Minimum spanning tree edges selected: \(A\)-\(D\)(31), \(D\)-\(E\)(40), \(A\)-\(H\)... [H deleted, so:] \(A\)-\(D\)(31), \(D\)-\(E\)(40), \(E\)-\(B\)(51), \(B\)-\(G\)(43), \(G\)-\(F\)(53), \(A\)-\(C\)(59) | M1 A1 | |
| MST weight \(= 31+40+40+43+43+53+... \) | ||
| Residual MST \(+ 2\) smallest edges from \(H\): \(H\)-\(A\)(41), \(H\)-\(C\)(45) | M1 | |
| Lower bound \(= \text{MST without }H + 41 + 45\) | A1 | |
| Lower bound \(= 267 + 41 + 49 = 357\) | A1 | Lower bound = 357 |
| Therefore \(357 \leq d \leq 371\) | A1 | Conclusion stated |
# Question 4:
## Part (i) – Nearest Neighbour from A:
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A \to D$ (31), $D \to E$ (40), $E \to B$ (51), $B \to G$ (43), $G \to F$ (53), $F \to H$ (49), $H \to C$ (45), $C \to A$ (59) | M1 A1 | M1 for correct method, A1 correct sequence |
| Total $= 31+40+51+43+53+49+45+59 = 371$ | A1 | Upper bound = 371 |
## Part (ii) – Prim's with H deleted:
| Answer | Marks | Guidance |
|--------|-------|----------|
| Starting from any node, applying Prim's to $\{A,B,C,D,E,F,G\}$ | M1 | |
| Minimum spanning tree edges selected: $A$-$D$(31), $D$-$E$(40), $A$-$H$... [H deleted, so:] $A$-$D$(31), $D$-$E$(40), $E$-$B$(51), $B$-$G$(43), $G$-$F$(53), $A$-$C$(59) | M1 A1 | |
| MST weight $= 31+40+40+43+43+53+... $ | | |
| Residual MST $+ 2$ smallest edges from $H$: $H$-$A$(41), $H$-$C$(45) | M1 | |
| Lower bound $= \text{MST without }H + 41 + 45$ | A1 | |
| Lower bound $= 267 + 41 + 49 = 357$ | A1 | Lower bound = 357 |
| Therefore $357 \leq d \leq 371$ | A1 | Conclusion stated |
---4. This question should be answered on the sheet provided.
A travelling salesman problem relates to the network represented by the following table of distances in kilometres. You may assume that the network satisfies the triangle inequality.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
& A & B & $C$ & D & $E$ & $F$ & G & $H$ \\
\hline
A & - & 85 & 59 & 31 & 47 & 52 & 74 & 41 \\
\hline
B & 85 & - & 104 & 73 & 51 & 68 & 43 & 55 \\
\hline
C & 59 & 104 & - & 54 & 62 & 88 & 61 & 45 \\
\hline
D & 31 & 73 & 54 & - & 40 & 59 & 65 & 78 \\
\hline
E & 47 & 51 & 62 & 40 & - & 56 & 71 & 68 \\
\hline
$F$ & 52 & 68 & 88 & 59 & 56 & - & 53 & 49 \\
\hline
G & 74 & 43 & 61 & 65 & 71 & 53 & - & 63 \\
\hline
H & 41 & 55 & 45 & 78 & 68 & 49 & 63 & - \\
\hline
\end{tabular}
\end{center}
Showing your method clearly, use\\
(i) the nearest neighbour algorithm, beginning with $A$,\\
(ii) Prim's algorithm with $H$ deleted,\\
to show that the minimum distance travelled, $d \mathrm {~km}$, satisfies the inequality $357 \leq d \leq 371$.\\
(11 marks)\\
\hfill \mbox{\textit{Edexcel D2 Q4 [11]}}