| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Route inspection starting and ending at same vertex |
| Difficulty | Moderate -0.3 This is a standard D1 route inspection problem with straightforward application of Dijkstra's algorithm and the Chinese Postman algorithm. Part (i) is routine shortest path, part (ii) requires identifying odd vertices and pairing them optimally (standard textbook procedure), and part (iii) is a minor variation. The question involves no novel insight—just methodical application of well-practiced algorithms with clear structure and moderate arithmetic. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks |
|---|---|
| Answer: Correct temporary labels at \(B\) to \(G\), no extras: \(B: 4, 11\); \(E: 8/9, 7\); \(G: 9/8, 7\); \(F: 6/7, 6\); \(H: 10/11, 8\); \(K: 11/10, 8\). Correct temporary labels at \(H\) to \(J\), no extras. All temporary labels correct. | M1, M1, A1 |
| Order of becoming permanent correct (follow through their permanent labels): \(A, D, G, J, K\). All permanent labels correct. | B1, B1 |
| Answer: Route \(A, D, G, J, K\); Number of speed cameras on route: 8 | B1, B1 |
| Answer | Marks |
|---|---|
| Answer: Odd nodes: \(A, I, J, K\). \(AI = 7\); \(AJ = 6\); \(AK = 8\); \(JK = 2\); \(IK = 4\); \(IJ = 6\). Weight of \(AI +\) weight of \(JK = 9\); Weight of \(AJ +\) weight of \(IK = 10\) (follow through weight of \(AI, AJ, AJ\) from (i) if necessary). | M1, A1, A1 |
| Repeat \(AI\) and \(JK \Rightarrow AB, BI\) and \(JK\). Route (example): \(K, J, D, A, B, I, K, J, G, K, H, G, F, E, C, G, D, C, A, B, C, E, B, I, E, K\). A list of 28 nodes that starts and ends with \(K\). Such a list that includes each of \(AB, BI, JK\) (or reversed) twice. | M1, A1 |
| Answer: Number of speed cameras on route: 81 | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: The only odd nodes are \(I\) and \(J\) so she only needs to repeat \(IJ = 6\); \(72 + 6 = 78\) | B1, M1, A1 | Identifying \(I\) and \(J\) (not just implied from 6 or 72+6 or 78). Correct calculation (may be implied from 78). |
**(i)**
Answer: Correct temporary labels at $B$ to $G$, no extras: $B: 4, 11$; $E: 8/9, 7$; $G: 9/8, 7$; $F: 6/7, 6$; $H: 10/11, 8$; $K: 11/10, 8$. Correct temporary labels at $H$ to $J$, no extras. All temporary labels correct. | M1, M1, A1 |
Order of becoming permanent correct (follow through their permanent labels): $A, D, G, J, K$. All permanent labels correct. | B1, B1 |
Answer: Route $A, D, G, J, K$; Number of speed cameras on route: 8 | B1, B1 |
**(ii)**
Answer: Odd nodes: $A, I, J, K$. $AI = 7$; $AJ = 6$; $AK = 8$; $JK = 2$; $IK = 4$; $IJ = 6$. Weight of $AI +$ weight of $JK = 9$; Weight of $AJ +$ weight of $IK = 10$ (follow through weight of $AI, AJ, AJ$ from (i) if necessary). | M1, A1, A1 |
Repeat $AI$ and $JK \Rightarrow AB, BI$ and $JK$. Route (example): $K, J, D, A, B, I, K, J, G, K, H, G, F, E, C, G, D, C, A, B, C, E, B, I, E, K$. A list of 28 nodes that starts and ends with $K$. Such a list that includes each of $AB, BI, JK$ (or reversed) twice. | M1, A1 |
Answer: Number of speed cameras on route: 81 | B1 |
**(iii)**
Answer: The only odd nodes are $I$ and $J$ so she only needs to repeat $IJ = 6$; $72 + 6 = 78$ | B1, M1, A1 | Identifying $I$ and $J$ (not just implied from 6 or 72+6 or 78). Correct calculation (may be implied from 78).
**Total: 16**
---5 Answer part (i) of this question on the insert provided.
Rhoda Raygh enjoys driving but gets extremely irritated by speed cameras.\\
The network represents a simplified map on which the arcs represent roads and the weights on the arcs represent the numbers of speed cameras on the roads.
The sum of the weights on the arcs is 72 .\\
\includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-05_874_1484_664_333}\\
(i) Rhoda lives at Ayton ( $A$ ) and works at Kayton ( $K$ ). Use Dijkstra's algorithm on the diagram in the insert to find the route from $A$ to $K$ that involves the least number of speed cameras and state the number of speed cameras on this route.\\
(ii) In her job Rhoda has to drive along each of the roads represented on the network to check for overhanging trees. This requires finding a route that covers every arc at least once, starting and ending at Kayton (K). Showing all your working, find a suitable route for Rhoda that involves the least number of speed cameras and state the number of speed cameras on this route.\\
(iii) If Rhoda checks the roads for overhanging trees on her way home, she will instead need a route that covers every arc at least once, starting at Kayton and ending at Ayton. Calculate the least number of speed cameras on such a route, explaining your reasoning.
\hfill \mbox{\textit{OCR D1 2007 Q5 [16]}}