| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Lower Bound by Vertex Deletion |
| Difficulty | Moderate -0.3 This is a standard D1 travelling salesman problem using textbook algorithms (nearest neighbour, vertex deletion lower bound). Part (i) is pure recall, parts (ii)-(iii) are routine application of algorithms taught explicitly in the syllabus, and part (iv) requires minimal insight since the answer is essentially given by the lower bound calculation. While multi-part with several marks, it requires no problem-solving beyond following prescribed procedures. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Travelling salesperson | B1 [1] | Identifying TSP by name |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(A - B - E - G - F - D - C - A\) | M1, A1 | For starting with \(A - B - E - G - \ldots\); For this closed tour |
| 130 (minutes) | B1 | For 130 |
| Shortest possible time \(\leq 130\) minutes | B1 [4] | For less than or equal to their time, with units |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Order of connecting: \(B, E, G, F, D, C\) | B1 | For a valid vertex order (or arc order) for their starting point |
| Tree connecting \(B, C, D, E, F\) and \(G\) but not \(A\) | M1, A1 | For a diagram or listing showing a tree connecting the vertices \(B, C, D, E, F\) and \(G\) but not \(A\); For a diagram showing one of these trees (vertices must be labelled but arc weights are not needed) |
| Lower bound \(= 10 + 15 + 95 = \mathbf{120}\) minutes | M1, M1, A1 [6] | For stating or using the total weight of their tree; For stating or using \(AB\) and \(AD\) or \(10 + 15\); For 120 or calculating \(25 +\) their 95, with units |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(A - B - E - G - F - C - D - A\) or this in reverse | M1, A1 [2] | For a reasonable attempt; For a valid tour of weight 125 |
# Question 3:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Travelling salesperson | B1 [1] | Identifying TSP by name |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A - B - E - G - F - D - C - A$ | M1, A1 | For starting with $A - B - E - G - \ldots$; For this closed tour |
| 130 (minutes) | B1 | For 130 |
| Shortest possible time $\leq 130$ minutes | B1 [4] | For less than or equal to their time, **with units** |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Order of connecting: $B, E, G, F, D, C$ | B1 | For a valid vertex order (or arc order) for their starting point |
| Tree connecting $B, C, D, E, F$ and $G$ but not $A$ | M1, A1 | For a diagram or listing showing a tree connecting the vertices $B, C, D, E, F$ and $G$ but not $A$; For a diagram showing one of these trees (vertices must be labelled but arc weights are not needed) |
| Lower bound $= 10 + 15 + 95 = \mathbf{120}$ minutes | M1, M1, A1 [6] | For stating or using the total weight of their tree; For stating or using $AB$ and $AD$ or $10 + 15$; For 120 or calculating $25 +$ their 95, **with units** |
## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A - B - E - G - F - C - D - A$ or this in reverse | M1, A1 [2] | For a reasonable attempt; For a valid tour of weight 125 |
---3 The network below represents a system of roads. The vertices represent villages and the arcs represent the roads between the villages. The weights on the arcs represent travel times by bicycle between villages, in minutes.\\
\includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-02_531_1113_1304_516}
Alf wants to cycle from his home at $A$ to visit each of the other villages and return to $A$ in the shortest possible time.\\
(i) Which standard network problem does Alf need to solve to find the quickest tour through all the villages?\\
(ii) Apply the nearest neighbour method starting at $A$ to find a tour through all the villages that starts and ends at $A$. Calculate the journey time for this tour. What can you deduce from this about the shortest possible time for Alf's tour?\\
(iii) Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex $A$ and all the arcs that are directly joined to $A$. Start building your tree at vertex $B$. (You do not need to represent the network as a matrix.)
Give the order in which vertices are added to your tree and draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Alf's journey time.\\
(iv) Write down a route for Alf that would take him 125 minutes.
\hfill \mbox{\textit{OCR D1 2006 Q3 [13]}}