| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Apply Kruskal's Algorithm |
| Difficulty | Moderate -0.8 This is a standard D1 question testing routine application of Kruskal's algorithm, deleted vertex method for TSP lower bound, and nearest neighbour algorithm for upper bound. All three parts follow textbook procedures with no problem-solving required—students simply execute well-practiced algorithms step-by-step. The 11 total marks reflect length rather than conceptual difficulty. |
| Spec | 7.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 |
| Answer | Marks |
|---|---|
| Using Kruskal's algorithm: Not selecting \(AC\) and \(DF\) | M1 |
| Selecting correct arcs in list, or implied (16+18+21+35+46+50, in this order with no others, can imply M1, A1) | A1 |
| Drawing a spanning tree for these six vertices | M1 |
| Correct (minimum) spanning tree drawn | A1 |
| Total weight = 186 | B1 |
| [5] |
| Answer | Marks |
|---|---|
| Delete \(BG\) from spanning tree: \(186 - 46 = 140\) | |
| Two shortest arcs from \(G\) are \(BG\) and \(EG\): \(140 + 46 + 55 = 241\) | |
| Lower bound = 241 | |
| Correct working for wrong vertex deleted can score B1, M1, A0 | B1 |
| Weight of MST on reduced network (if from part (i)) | M1 |
| Adding two shortest arcs to MST: 241 | A1 |
| [3] |
| Answer | Marks |
|---|---|
| \(A-D-C-F-G-\ldots\) or \(16+18+21+58+\ldots\) | M1 |
| \(A-D-C-F-G-B-E-A\) | A1 |
| Upper bound = 274 | B1 |
| Using nearest neighbour: Correct closed tour listed, not just weights added | A1 |
| [3] |
## (i)
Using Kruskal's algorithm: Not selecting $AC$ and $DF$ | M1 |
Selecting correct arcs in list, or implied (16+18+21+35+46+50, in this order with no others, can imply M1, A1) | A1 |
Drawing a spanning tree for these six vertices | M1 |
Correct (minimum) spanning tree drawn | A1 |
Total weight = 186 | B1 |
| [5] |
## (ii)
Delete $BG$ from spanning tree: $186 - 46 = 140$ | |
Two shortest arcs from $G$ are $BG$ and $EG$: $140 + 46 + 55 = 241$ | |
Lower bound = 241 | |
Correct working for wrong vertex deleted can score B1, M1, A0 | B1 |
Weight of MST on reduced network (if from part (i)) | M1 |
Adding two shortest arcs to MST: 241 | A1 |
| [3] |
## (iii)
$A-D-C-F-G-\ldots$ or $16+18+21+58+\ldots$ | M1 |
$A-D-C-F-G-B-E-A$ | A1 |
Upper bound = 274 | B1 |
Using nearest neighbour: Correct closed tour listed, not just weights added | A1 |
| [3] |
---Answer this question on the insert provided.
\includegraphics{figure_2}
\begin{enumerate}[label=(\roman*)]
\item This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight. [5]
\item Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex $G$, and all the arcs joined to $G$, removed. Hence find a lower bound for the travelling salesperson problem on the original network. [3]
\item Apply the nearest neighbour method, starting from vertex $A$, to find an upper bound for the travelling salesperson problem on the original network. [3]
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2008 Q3 [11]}}