| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Session | Specimen |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Identify Best Lower Bound |
| Difficulty | Moderate -0.5 This is a standard application of the deletion method for finding lower bounds in TSP, followed by nearest-neighbour algorithm - both are routine D2 procedures requiring only methodical application of learned algorithms with no novel problem-solving or insight needed. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Notes |
| Deleting \(F\) leaves r.s.t | M1 | |
| r.s.t length \(= 86\), lower bound \(= 86 + 16 + 19 = 121\) | A1 | |
| M1 A1 | (4 marks) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Notes |
| Best \(LB\) is 129 by deleting \(C\) | B1 ft | (1 mark) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Notes |
| Add 33 to \(BF\) and \(FB\) | B1 | |
| Add 31 to \(DE\) and \(ED\) | B1 | (2 marks) |
| Tour visits each vertex, order correct using table of least distances | M1 A1 | |
| e.g. \(FCDABEGF\) (actual route \(FCDCABEGF\)) | A1 | |
| Upper bound of 138 km | A1 | (4 marks) |
# Question 4:
## Part (a)
| Answer/Working | Marks | Notes |
|---|---|---|
| Deleting $F$ leaves r.s.t | M1 | |
| r.s.t length $= 86$, lower bound $= 86 + 16 + 19 = 121$ | A1 | |
| | M1 A1 | (4 marks) |
## Part (b)
| Answer/Working | Marks | Notes |
|---|---|---|
| Best $LB$ is 129 by deleting $C$ | B1 ft | (1 mark) |
## Part (c)
| Answer/Working | Marks | Notes |
|---|---|---|
| Add 33 to $BF$ and $FB$ | B1 | |
| Add 31 to $DE$ and $ED$ | B1 | (2 marks) |
| Tour visits each vertex, order correct using table of least distances | M1 A1 | |
| e.g. $FCDABEGF$ (actual route $FCDCABEGF$) | A1 | |
| Upper bound of 138 km | A1 | (4 marks) |
**Total: 11 marks**
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{899a26d1-7599-4051-b1cf-596542624997-5_602_1255_196_406}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
The network in Figure 2 shows the distances, in km , of the cables between seven electricity relay stations $A , B , C , D , E , F$ and $G$. An inspector needs to visit each relay station. He wishes to travel a minimum distance, and his route must start and finish at the same station.
By deleting C, a lower bound for the length of the route is found to be 129 km .
\begin{enumerate}[label=(\alph*)]
\item Find another lower bound for the length of the route by deleting $F$. State which is the best lower bound of the two.
\item By inspection, complete the table of least distances.
The table can now be taken to represent a complete network.
\item Using the nearest-neighbour algorithm, starting at $F$, obtain an upper bound to the length of the route. State your route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q4 [11]}}