| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2005 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Lower Bound by Vertex Deletion |
| Difficulty | Standard +0.3 This is a standard application of lower bound by vertex deletion and nearest-neighbour algorithm from the D2 specification. The question follows a routine template: delete a vertex, find MST of remainder plus two cheapest edges, then apply nearest-neighbour. While it requires multiple steps and careful arithmetic, it involves no novel problem-solving or insight beyond direct application of learned algorithms. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
I notice you've provided a question header "Question 2:" but no actual mark scheme content to clean up.
Please provide the mark scheme content that needs to be converted to LaTeX notation and formatted.2.\\
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-1_613_1269_1318_392}
The network in the diagram 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 better 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.\\
(4) (Total 11 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2005 Q2 [11]}}