| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 17 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | MST Method for Upper Bound |
| Difficulty | Standard +0.8 This is a multi-part Travelling Salesman Problem requiring multiple algorithms (nearest neighbour, MST method, lower bound by deletion). While the individual techniques are standard D2 content, the question demands careful application of several methods, interpretation of a network diagram, and strategic use of shortcuts to improve bounds. The five-part structure and need to synthesize results into a final interval makes this more demanding than typical textbook exercises, though still within expected D2 scope. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| Stage | Previous tournament | Current tournament | ||||
| \multirow[t]{3}{*}{1} | G |
| ||||
| \(H\) |
| |||||
| I |
| |||||
| \multirow[t]{3}{*}{2} | D |
| ||||
| \(E\) |
| |||||
| \(F\) |
| |||||
| \multirow[t]{3}{*}{3} | A |
| ||||
| \(B\) |
| |||||
| C |
| |||||
| 4 | None |
|
| Answer | Marks | Guidance |
|---|---|---|
| Shortest distances by inspection (e.g. \(A\)-\(D\) via appropriate route) stated in complete network | M1 A1 A1 | M1 method, A1 A1 for correct distances |
| Answer | Marks |
|---|---|
| Nearest neighbour from \(A\): \(A \to B(36) \to C(44) \to D(19) \to E(38) \to F(27) \to A(53)\) | M1 A1 |
| Upper bound \(= 36+44+19+38+27+53 = 217\) miles | A1 |
| Answer | Marks |
|---|---|
| Minimum spanning tree (e.g. Prim's/Kruskal's): include edges totalling minimum | M1 A1 |
| Double MST to give upper bound | A1 |
| Answer | Marks |
|---|---|
| Apply two shortcuts to reduce upper bound below 225 | M1 A1 A1 A1 |
| Answer | Marks |
|---|---|
| Delete \(A\) and find MST of remaining 5 nodes | M1 A1 |
| Add two smallest edges from \(A\): lower bound \(=\) MST \(+ \) two smallest arcs from \(A\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| \(d\) lies in interval [lower bound, upper bound from (c)(ii)] | B1 | ft their bounds |
# Question 6:
## Part (a)
| Shortest distances by inspection (e.g. $A$-$D$ via appropriate route) stated in complete network | M1 A1 A1 | M1 method, A1 A1 for correct distances |
## Part (b)
| Nearest neighbour from $A$: $A \to B(36) \to C(44) \to D(19) \to E(38) \to F(27) \to A(53)$ | M1 A1 | |
| Upper bound $= 36+44+19+38+27+53 = 217$ miles | A1 | |
## Part (c)(i)
| Minimum spanning tree (e.g. Prim's/Kruskal's): include edges totalling minimum | M1 A1 | |
| Double MST to give upper bound | A1 | |
## Part (c)(ii)
| Apply two shortcuts to reduce upper bound below 225 | M1 A1 A1 A1 | |
## Part (d)
| Delete $A$ and find MST of remaining 5 nodes | M1 A1 | |
| Add two smallest edges from $A$: lower bound $=$ MST $+ $ two smallest arcs from $A$ | A1 | |
## Part (e)
| $d$ lies in interval [lower bound, upper bound from (c)(ii)] | B1 | ft their bounds |
I can see these are answer sheets for students (not a mark scheme) - they show the question structure/tables for students to fill in their answers for Questions 2 and 6.
These pages contain:
- **Question 2**: A blank table for students to complete, with columns for Stage, Previous tournament, and Current tournament (showing a tournament/competition structure with players A-L across 4 stages)
- **Question 6**: Answer sheets with a graph/network diagram (nodes A-F with weighted edges) and blank spaces for parts (a), (b), (c)(i), (c)(ii), (d), and (e)
**I cannot extract mark scheme content from these pages** because they are student answer sheets, not a mark scheme. They contain no mark allocations, model answers, or examiner guidance.
If you have the actual mark scheme document for this paper (Solomon Press D2F), I would be happy to extract and format that content for you.6. This question should be answered on the sheet provided.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{073926c5-03cc-41d4-82bf-315740ead663-6_672_984_322_431}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
A band is going on tour to play gigs in six towns, including their home town, $A$. The network in Figure 1 shows the distances, in miles, between the various towns. The band must begin and end their tour at $A$ and visit each of the other towns once, and they wish to keep the total distance travelled as small as possible.
\begin{enumerate}[label=(\alph*)]
\item By inspection, draw a complete network showing the shortest distances between the towns.
\item Use your complete network and the nearest neighbour algorithm, starting at $A$, to find an upper bound for the total distance travelled.
\item \begin{enumerate}[label=(\roman*)]
\item Use your complete network to obtain and draw a minimum spanning tree and hence obtain another upper bound for the total distance travelled.
\item Improve this upper bound using two shortcuts to find an upper bound below 225 miles.
\end{enumerate}\item By deleting $A$, find a lower bound for the total distance travelled.
\item State an interval of as small a width as possible within which $d$, the minimum distance travelled, in miles, must lie.
\section*{Please hand this sheet in for marking}
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
Stage & Previous tournament & Current tournament & \\
\hline
\multirow[t]{3}{*}{1} & G & \begin{tabular}{l}
J \\
K \\
L \\
\end{tabular} & \\
\hline
& $H$ & \begin{tabular}{l}
J \\
K \\
L \\
\end{tabular} & \\
\hline
& I & \begin{tabular}{l}
J \\
K \\
L \\
\end{tabular} & \\
\hline
\multirow[t]{3}{*}{2} & D & \begin{tabular}{l}
G \\
H \\
I \\
\end{tabular} & \\
\hline
& $E$ & \begin{tabular}{l}
G \\
H \\
I \\
\end{tabular} & \\
\hline
& $F$ & \begin{tabular}{l}
G \\
H \\
I \\
\end{tabular} & \\
\hline
\multirow[t]{3}{*}{3} & A & \begin{tabular}{l}
D \\
E \\
F \\
\end{tabular} & \\
\hline
& $B$ & \begin{tabular}{l}
D \\
E \\
F \\
\end{tabular} & \\
\hline
& C & \begin{tabular}{l}
D \\
E \\
F \\
\end{tabular} & \\
\hline
4 & None & \begin{tabular}{l}
A \\
B \\
C \\
\end{tabular} & \\
\hline
\end{tabular}
\end{center}
\section*{Please hand this sheet in for marking}
(a)\\
\includegraphics[max width=\textwidth, alt={}, center]{073926c5-03cc-41d4-82bf-315740ead663-8_684_992_461_427}\\
(b)
\section*{Sheet for answering question 6 (cont.)}
(c) (i)\\
(ii) $\_\_\_\_$\\
(d)\\
(e) $\_\_\_\_$
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q6 [17]}}