| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2002 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Lower Bound by Vertex Deletion |
| Difficulty | Moderate -0.3 This is a standard D2 travelling salesman question following a predictable three-part structure: apply Prim's algorithm (routine), find upper bound via MST doubling with shortcuts (standard technique), and calculate lower bound by vertex deletion (algorithmic procedure). While it requires multiple steps and careful arithmetic with a 6×6 table, all techniques are textbook exercises with no novel problem-solving or insight required, making it slightly easier than average. |
| 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 method7.04d Travelling salesman lower bound: using minimum spanning tree |
| \cline { 2 - 7 } \multicolumn{1}{c|}{} | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) |
| \(A\) | - | 85 | 110 | 175 | 108 | 100 |
| \(B\) | 85 | - | 38 | 175 | 160 | 93 |
| \(C\) | 110 | 38 | - | 148 | 156 | 73 |
| \(D\) | 175 | 175 | 148 | - | 110 | 84 |
| \(E\) | 108 | 160 | 156 | 110 | - | 92 |
| \(F\) | 100 | 93 | 73 | 84 | 92 | - |
6. The table below shows the distances, in km, between six towns $A , B , C , D , E$ and $F$.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\cline { 2 - 7 }
\multicolumn{1}{c|}{} & $A$ & $B$ & $C$ & $D$ & $E$ & $F$ \\
\hline
$A$ & - & 85 & 110 & 175 & 108 & 100 \\
\hline
$B$ & 85 & - & 38 & 175 & 160 & 93 \\
\hline
$C$ & 110 & 38 & - & 148 & 156 & 73 \\
\hline
$D$ & 175 & 175 & 148 & - & 110 & 84 \\
\hline
$E$ & 108 & 160 & 156 & 110 & - & 92 \\
\hline
$F$ & 100 & 93 & 73 & 84 & 92 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Starting from $A$, use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected.\\
(4)
\item \begin{enumerate}[label=(\roman*)]
\item Using your answer to part (a) obtain an initial upper hound for the solution of the travelling salesman problem.
\item Use a short cut to reduce the upper bound to a value less than 680 .\\
(4)
\end{enumerate}\item Starting by deleting $F$, find a lower bound for the solution of the travelling salesman problem.\\
(4)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2002 Q6 [12]}}