| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Lower Bound by Vertex Deletion |
| Difficulty | Standard +0.3 This is a standard D1 travelling salesman problem using two routine algorithms (vertex deletion for lower bound and nearest neighbour). Both methods are algorithmic procedures taught directly in the specification with minimal problem-solving required. The question is slightly above average difficulty only because it requires careful execution of two separate algorithms and interpretation of a network diagram, but involves no novel insight or proof. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
3 The diagram shows a network. The weights on the arcs represent distances in miles. The direct path between any two adjacent vertices is never longer than any indirect path.\\
\includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-02_490_748_1372_699}\\
(i) By deleting vertex $U$ and all arcs connected to $U$, find a lower bound for the length of the shortest cycle that visits every vertex of this network.\\
(ii) Find a vertex that can be used as the start vertex for the nearest neighbour method to give a cycle that passes through every vertex of this network. Give your cycle and its length.
\hfill \mbox{\textit{OCR D1 2005 Q3 [7]}}