| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Combined Dijkstra and route inspection |
| Difficulty | Standard +0.3 This is a straightforward application of two standard D1 algorithms (Dijkstra and route inspection) with minimal problem-solving required. Part (i) is routine Dijkstra execution, part (ii) is textbook route inspection (identify odd vertices, pair them, add repeats), and part (iii) simply asks students to name the travelling salesman problem. The question is slightly easier than average because it's highly structured with clear instructions for each algorithmic step. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| (i) | ||
| M1 | For correct initial temporary labels at \(F\), \(G\), \(I\) | |
| M1 | For correctly updating \(F\) and label at \(H\) | |
| A1 | For all temporary labels correct (including \(J\)) (allow extra 100 at C, 105 at D, 75 at H only) | |
| Shortest path from J to B: \(J \; G \; H \; E \; B\) Length of path: 125 metres | B1, B1, 7 | For correct route (condone omission of J or B) For 125 |
| (ii) | Odd nodes: \(B \; C \; E \; J\) | B1 |
| \(BC = 60\) \(BE = 35\) \(BJ = 125\) \(EJ = 90\) \(C_I = 95\) \(CE = 70\) | M1 | For any three of these weights correct, or implied or from their (i) |
| Repeat \(BE\) and \(CJ\) (or \(BE\), \(JI\), \(IC\)) | A1 | For identifying the pairing \(BE\), \(CJ\) to repeat or 130 (not \(\pi\)) |
| \(130 + 765\) Shortest route: 895 metres | M1, A1, 5 | For \(765 +\) their 130 (a valid pairs total) For 895 (cao) |
| (iii) | B1 | |
| M1 | For a reasonable attempt at arc weights (at least 9 correct, including the three given) | |
| A1 | For all arc weights correct | |
| Travelling salesperson problem | B1, 16 | For identifying TSP by name |
(i) | | | ANSWERED ON INSERT
| | M1 | For correct initial temporary labels at $F$, $G$, $I$
| | M1 | For correctly updating $F$ and label at $H$
| | A1 | For all temporary labels correct (including $J$) (allow extra 100 at C, 105 at D, 75 at H only)
| Shortest path from J to B: $J \; G \; H \; E \; B$ Length of path: 125 metres | B1, B1, 7 | For correct route (condone omission of J or B) For 125
(ii) | Odd nodes: $B \; C \; E \; J$ | B1 | For identifying or using $B \; C \; E \; J$ or implied
| $BC = 60$ $BE = 35$ $BJ = 125$ $EJ = 90$ $C_I = 95$ $CE = 70$ | M1 | For any three of these weights correct, or implied or from their (i)
| Repeat $BE$ and $CJ$ (or $BE$, $JI$, $IC$) | A1 | For identifying the pairing $BE$, $CJ$ to repeat or 130 (not $\pi$)
| $130 + 765$ Shortest route: 895 metres | M1, A1, 5 | For $765 +$ their 130 (a valid pairs total) For 895 (cao)
(iii) | | B1 | For graph structure correct
| | M1 | For a reasonable attempt at arc weights (at least 9 correct, including the three given)
| | A1 | For all arc weights correct
| Travelling salesperson problem | B1, 16 | For identifying TSP by name
---5 Answer this question on the insert provided.
The network below represents a simplified map of a building. The arcs represent corridors and the weights on the arcs represent the lengths of the corridors, in metres.
The sum of the weights on the arcs is 765 metres.\\
\includegraphics[max width=\textwidth, alt={}, center]{dbf782dd-879c-4f0f-b532-246a0db9f130-5_1271_1539_584_303}\\
(i) Janice is the cleaning supervisor in the building. She is at the position marked as J when she is called to attend a cleaning emergency at B. On the network in the insert, use Dijkstra's algorithm, starting from vertex J and continuing until B is given a permanent label, to find the shortest path from J to B and the length of this path.\\
(ii) In her job J anice has to walk along each of the corridors represented on the network. This requires finding a route that covers every arc at least once, starting and ending at J. Showing all your working, find the shortest distance that J anice must walk to check all the corridors.
The labelled vertices represent 'cleaning stations'. J anice wants to visit every cleaning station using the shortest possible route. She produces a simplified network with no repeated arcs and no arc that joins a vertex to itself.\\
(iii) On the insert, complete Janice's simplified network. Which standard network problem does Janice need to solve to find the shortest distance that she must travel?
\hfill \mbox{\textit{OCR D1 2007 Q5 [16]}}