| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Lower Bound by Vertex Deletion |
| Difficulty | Moderate -0.5 This is a standard textbook application of the vertex deletion method for finding TSP bounds. Students follow a mechanical algorithm: delete vertex A, find MST of remaining graph, add two smallest edges from A. The procedure is routine for D1 students who have practiced this technique, requiring careful arithmetic but no problem-solving insight or novel approaches. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| ↓ | |||||||
| \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | \(G\) | |
| A | 0 | 4 | 5 | 3 | 2 | 5 | 6 |
| \(B\) | 4 | 0 | 1 | 2 | 4 | 7 | 6 |
| C | 5 | 1 | 0 | 3 | 4 | 6 | 7 |
| \(D\) | 3 | 2 | 3 | 0 | 2 | 6 | 4 |
| \(E\) | 2 | 4 | 4 | 2 | 0 | 6 | 6 |
| \(F\) | 5 | 7 | 6 | 6 | 6 | 0 | 10 |
| \(G\) | 6 | 6 | 7 | 4 | 6 | 10 | 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: [Table shows minimum spanning tree with order \(A, E, D, B, C, G, F\) and edges connecting them]. Total weight: 16 (or 1600 m) | M1, M1 dep, A1, B1, B1, B1 | FIRST THREE MARKS ARE FOR WORK ON THE TABLE ONLY (Starting by choosing row E in column A). Choosing more than one entry from column A. Correct entries chosen (or all transposed). Correct order, listed or marked on arrows or table, or arcs listed \(AE, ED, DB, BC, DG, AF\). Tree (correct or follow through from table, provided solution forms a spanning tree). 16 or 1600m (or follow through from table or diagram, provided solution forms a spanning tree). |
| Answer | Marks |
|---|---|
| Answer: Travelling salesman (problem) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Two shortest arcs from \(H\): \(12 + 13 = 25\); \(25 + 16 = 41\) | B1, M1 | Identifying TSP by name. Adding their 25 to their 16 or 41 (must be using two arcs from \(H\)). |
| Answer: 4100 m | A1 | 4100 m or 4.1 km (correct and with units). |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(H, A, E, D, B, C, F, G, H\) | M1, A1 | \((H) A, E, D, B, C, \ldots\). Correct tour. |
| Answer: \(12+2+2+2+1+6+10+16 = 51\); 5100 m | M1, A1 | A substantially correct attempt at sum. 5100 m or 5.1 km (correct and with units). |
**(i)**
Answer: [Table shows minimum spanning tree with order $A, E, D, B, C, G, F$ and edges connecting them]. Total weight: 16 (or 1600 m) | M1, M1 dep, A1, B1, B1, B1 | **FIRST THREE MARKS ARE FOR WORK ON THE TABLE ONLY** (Starting by choosing row E in column A). Choosing more than one entry from column A. Correct entries chosen (or all transposed). Correct order, listed or marked on arrows or table, or arcs listed $AE, ED, DB, BC, DG, AF$. Tree (correct or follow through from table, provided solution forms a spanning tree). 16 or 1600m (or follow through from table or diagram, provided solution forms a spanning tree).
**(ii)**
Answer: Travelling salesman (problem) | B1 |
**(iii)**
Answer: Two shortest arcs from $H$: $12 + 13 = 25$; $25 + 16 = 41$ | B1, M1 | Identifying TSP by name. Adding their 25 to their 16 or 41 (must be using two arcs from $H$).
Answer: 4100 m | A1 | 4100 m or 4.1 km (correct and with units).
**(iv)**
Answer: $H, A, E, D, B, C, F, G, H$ | M1, A1 | $(H) A, E, D, B, C, \ldots$. Correct tour.
Answer: $12+2+2+2+1+6+10+16 = 51$; 5100 m | M1, A1 | A substantially correct attempt at sum. 5100 m or 5.1 km (correct and with units).
**Total: 14**
---4 (i)
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
\multicolumn{8}{|c|}{↓} \\
\hline
& $A$ & $B$ & $C$ & $D$ & $E$ & $F$ & $G$ \\
\hline
A & 0 & 4 & 5 & 3 & 2 & 5 & 6 \\
\hline
$B$ & 4 & 0 & 1 & 2 & 4 & 7 & 6 \\
\hline
C & 5 & 1 & 0 & 3 & 4 & 6 & 7 \\
\hline
$D$ & 3 & 2 & 3 & 0 & 2 & 6 & 4 \\
\hline
$E$ & 2 & 4 & 4 & 2 & 0 & 6 & 6 \\
\hline
$F$ & 5 & 7 & 6 & 6 & 6 & 0 & 10 \\
\hline
$G$ & 6 & 6 & 7 & 4 & 6 & 10 & 0 \\
\hline
\end{tabular}
\end{center}
Order in which rows were deleted: $\_\_\_\_$ $A$
Minimum spanning tree:
A
\begin{itemize}
\item $D$
\end{itemize}
F\\
B
E\\
\includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_33_28_1302_1101}
III\\
o
D
C\\
\includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_38_38_1297_1491}\\
•
G
Total weight: $\_\_\_\_$\\
(ii) $\_\_\_\_$\\
(iii) $\_\_\_\_$\\
Lower bound: $\_\_\_\_$\\
(iv) Tour: $\_\_\_\_$\\
Upper bound: $\_\_\_\_$
\hfill \mbox{\textit{OCR D1 2007 Q4 [14]}}