| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Combined Dijkstra and route inspection |
| Difficulty | Challenging +1.2 This is a multi-part route inspection question combining Dijkstra's algorithm with Chinese Postman problem concepts. Parts (i)-(ii) are standard Dijkstra application (routine for D1). Part (iii) is conceptual recall about odd vertices. Part (iv) is standard Chinese Postman requiring identification of odd vertices and pairing. Part (v) adds a novel constraint about the partial completion scenario, requiring students to adapt the route inspection method to a modified network, which elevates it slightly above typical textbook exercises but remains within expected D1 problem-solving scope. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct order of labelling: A=0, B=200, C=500, D=350, E=430, F=500, G=530, H=700 | M1 | Method for Dijkstra shown |
| Working values updated correctly at each stage | A1 | All working values correct |
| Correct permanent labels in correct order | A1 | |
| Route traced back correctly: A-B-D-F-H | A1 | |
| Shortest distance = 700 | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A to E: A-B-D-E, distance 430 | B1 | |
| A to G: A-B-D-E-G, distance 530 | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| The graph has vertices of odd degree (more than two), so an Eulerian circuit does not exist | B1 | Must reference odd degree vertices |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Identify odd vertices: B, C, E, H (or similar correct identification) | M1 | |
| Find minimum matching of odd vertices e.g. BC+EH = 500+100=600, BE+CH = 430+..., BH+CE=... | M1 | Consider all pairings |
| Total = 2200 + minimum repeat = 2200 + 580 | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Nadia and Sheng-Li together travel A-B-C-E (covering AB=200, BC=500, CE=150) | M1 | Identifying what has been covered |
| Sheng-Li travels E-C-A covering EC and CA (one side) | M1 | |
| Remaining streets for Nadia identified: all streets not yet covered twice | M1 | |
| Minimum distance calculated with justification that it is minimum | A1 | Full explanation required |
# Question 5:
## Part (i) - Dijkstra's Algorithm [5 marks]
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct order of labelling: A=0, B=200, C=500, D=350, E=430, F=500, G=530, H=700 | M1 | Method for Dijkstra shown |
| Working values updated correctly at each stage | A1 | All working values correct |
| Correct permanent labels in correct order | A1 | |
| Route traced back correctly: A-B-D-F-H | A1 | |
| Shortest distance = 700 | A1 | |
## Part (ii) - Shortest Routes [2 marks]
| Answer | Marks | Guidance |
|--------|-------|----------|
| A to E: A-B-D-E, distance 430 | B1 | |
| A to G: A-B-D-E-G, distance 530 | B1 | |
## Part (iii) - Why streets must be repeated [1 mark]
| Answer | Marks | Guidance |
|--------|-------|----------|
| The graph has vertices of odd degree (more than two), so an Eulerian circuit does not exist | B1 | Must reference odd degree vertices |
## Part (iv) - Shortest route for Chinese Postman [3 marks]
| Answer | Marks | Guidance |
|--------|-------|----------|
| Identify odd vertices: B, C, E, H (or similar correct identification) | M1 | |
| Find minimum matching of odd vertices e.g. BC+EH = 500+100=600, BE+CH = 430+..., BH+CE=... | M1 | Consider all pairings |
| Total = 2200 + minimum repeat = 2200 + 580 | A1 | cao |
## Part (v) - Minimum distance for Nadia [4 marks]
| Answer | Marks | Guidance |
|--------|-------|----------|
| Nadia and Sheng-Li together travel A-B-C-E (covering AB=200, BC=500, CE=150) | M1 | Identifying what has been covered |
| Sheng-Li travels E-C-A covering EC and CA (one side) | M1 | |
| Remaining streets for Nadia identified: all streets not yet covered twice | M1 | |
| Minimum distance calculated with justification that it is minimum | A1 | Full explanation required |
---5 The network below represents the streets in a small village. The weights on the arcs show distances in metres. The total length of all the streets shown is 2200 metres.\\
\includegraphics[max width=\textwidth, alt={}, center]{372c062a-793f-4fb8-a769-957479f5fce7-07_499_1264_367_402}\\
(i) Apply Dijkstra's algorithm to the network, starting at $A$, to find the shortest route from $A$ to $H$.\\
(ii) Write down the shortest route from $A$ to $E$ and the shortest route from $A$ to $G$.
Sheng-Li needs to travel along every street to deliver leaflets. He will start and finish at $A$.\\
(iii) Explain why Sheng-Li will need to repeat some streets.\\
(iv) Showing your working, find the length of the shortest route that Sheng-Li can take, starting and ending at $A$, to deliver leaflets to every street.
The streets have houses on both sides. Sheng-Li does not want to keep crossing the streets from one side to the other. His friend Nadia offers to help him. They decide that they will work together and set off from $A$, with Sheng-Li delivering to one side of $A B$ and Nadia delivering to the other side. Each street will have to be travelled along twice, either by both of them travelling along it once or by one of them travelling along it twice.
Nadia and Sheng-Li travel $A - B - C - E$. At this point Sheng-Li is called back to $A$. He travels along $E - C - A$, delivering leaflets on one side of $C A$. Nadia completes the leaflet delivery on her own.\\
(v) Calculate the minimum distance that Nadia will need to travel on her own to complete the delivery. Explain how your answer was achieved and how you know that it is the minimum possible distance.\\[0pt]
[4]
\hfill \mbox{\textit{OCR D1 2015 Q5 [15]}}