| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | January |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra combined with Chinese Postman |
| Difficulty | Standard +0.3 This is a standard D1 question combining routine Dijkstra's algorithm (part i) with Chinese Postman problem (parts ii-iii). Both are textbook applications requiring systematic execution of learned algorithms rather than problem-solving insight. The multi-part structure and need to identify odd vertices adds modest complexity, but these are core D1 topics tested in predictable ways, making this slightly easier than average overall. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct temporary labels at each vertex | M1 | Must show working at each vertex |
| Permanent labels: \(A=0(1), B=8(2), C=5(3), D=9(5), E=9(4), F=15(6), G=10(6), H=16(7)\) | A1 | Order of permanent labelling shown |
| Correct order of permanent labelling shown | A1 | |
| Route: \(A \to C \to D \to G \to F \to E \to H\) | A1 | |
| Minimum traffic lights = 16 | A1 | [5] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Identify odd vertices | M1 | Odd vertices are \(A, B, E, H\) (orders 1, 3, 3, 3) or correct identification |
| List pairings and find weights of paths between odd vertices | M1 | |
| Minimum matching found | A1 | |
| Minimum repeat = correct value stated | A1 | [4] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| For semi-Eulerian path need exactly 2 odd vertices | B1 | D and H must be the two odd vertices |
| Correct identification of which vertices need to be made even | M1 | |
| Route stated with minimum repeats explained | A1 | [3] |
# Question 1:
## Part (i) - Dijkstra's Algorithm
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct temporary labels at each vertex | M1 | Must show working at each vertex |
| Permanent labels: $A=0(1), B=8(2), C=5(3), D=9(5), E=9(4), F=15(6), G=10(6), H=16(7)$ | A1 | Order of permanent labelling shown |
| Correct order of permanent labelling shown | A1 | |
| Route: $A \to C \to D \to G \to F \to E \to H$ | A1 | |
| Minimum traffic lights = 16 | A1 | **[5]** |
## Part (ii) - Chinese Postman from D (Eulerian circuit)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Identify odd vertices | M1 | Odd vertices are $A, B, E, H$ (orders 1, 3, 3, 3) or correct identification |
| List pairings and find weights of paths between odd vertices | M1 | |
| Minimum matching found | A1 | |
| Minimum repeat = correct value stated | A1 | **[4]** |
## Part (iii) - Route from D to H
| Answer | Marks | Guidance |
|--------|-------|----------|
| For semi-Eulerian path need exactly 2 odd vertices | B1 | D and H must be the two odd vertices |
| Correct identification of which vertices need to be made even | M1 | |
| Route stated with minimum repeats explained | A1 | **[3]** |
---1 In the network below, the arcs represent the roads in Ayton, the vertices represent roundabouts, and the arc weights show the number of traffic lights on each road. Sam is an evening class student at Ayton Academy ( $A$ ). She wants to drive from the academy to her home ( $H$ ). Sam hates waiting at traffic lights so she wants to find the route for which the number of traffic lights is a minimum.\\
\includegraphics[max width=\textwidth, alt={}, center]{bb7fb141-ef42-42af-b052-d8e20d6e5157-02_786_1097_482_523}\\
(i) Apply Dijkstra's algorithm to find the route that Sam should use to travel from $A$ to $H$. At each vertex, show the temporary labels, the permanent label and the order of permanent labelling.
In the daytime, Sam works for the highways department. After an electrical storm, the highways department wants to check that all the traffic lights are working. Sam is sent from the depot ( $D$ ) to drive along every road and return to the depot. Sam needs to pass every traffic light, but wants to repeat as few as possible.\\
(ii) Find the minimum number of traffic lights that must be repeated. Show your working.
Suppose, instead, that Sam wants to start at the depot, drive along every road and end at her home, passing every traffic light but repeating as few as possible.\\
(iii) Find a route on which the minimum number of traffic lights must be repeated. Explain your reasoning.
\hfill \mbox{\textit{OCR D1 2011 Q1 [12]}}