| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Effect of adding/removing edge |
| Difficulty | Standard +0.3 This is a standard route inspection problem requiring identification of odd vertices and systematic pairing to minimize repeated edges. Part (i) is routine application of the Chinese Postman algorithm, while part (ii) requires recalculating after a network change—methodical but straightforward for D1 students who know the algorithm. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied: temporary/permanent labels at \(B\): 24; \(C\): 45; \(D\): 18; \(E\): 25; \(F\): 42; \(G\): 47 (then 51, 47); \(H\): 37 (then 54, 37); \(J\): 48 | M1 | Values correct at \(B\), \(D\) and \(E\) (condone temporary labels implied from permanent labels) |
| Both 54 and 37 seen at \(H\) and both 51 and 47 seen at \(G\) | M1 | Method shown |
| All temporary labels correct and no extras | A1 | |
| All permanent labels correct | B1 | |
| Order of labelling correct (condone boxes consistently swapped over) | B1 | |
| Route: \(A - E - H - J\); 48 metres | B1, B1 [7] | For this route including end vertices (cao); For 48 (cao) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(A\) and \(J\) are the only odd nodes | B1 | Identifying odd nodes (or by implication) |
| \(48 + 300 = \mathbf{348}\) metres | M1, A1 [3] | For their \(48 + 300\) (or their 300); 348 (cao) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Odd nodes \(A, B, H, J\) | B1 | Identifying odd nodes (or by implication) |
| \(AB = 24\); \(AH = 37\); \(AJ = 48\) | B1 | For distances from \(A\) – or from their Dijkstra |
| \(HJ = 11\); \(BJ = 38\); \(BH = 34\) | B1 | For distances \(HJ\), \(BJ\), \(BH\) correct |
| Repeat \(AB\) and \(HJ = 35\) | M1, M1 | Choosing their least pairing or by implication |
| \(300 - 30 = 270\) metres | Or by implication | |
| Shortest distance \(= 270 + 35 = \mathbf{305}\) metres | A1 [6] | 305 (cao) |
# Question 6:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied: temporary/permanent labels at $B$: 24; $C$: 45; $D$: 18; $E$: 25; $F$: 42; $G$: 47 (then 51, 47); $H$: 37 (then 54, 37); $J$: 48 | M1 | Values correct at $B$, $D$ and $E$ (condone temporary labels implied from permanent labels) |
| Both 54 and 37 seen at $H$ and both 51 and 47 seen at $G$ | M1 | Method shown |
| All temporary labels correct and no extras | A1 | |
| All permanent labels correct | B1 | |
| Order of labelling correct (condone boxes consistently swapped over) | B1 | |
| Route: $A - E - H - J$; **48** metres | B1, B1 [7] | For this route including end vertices (cao); For 48 (cao) |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A$ and $J$ are the only odd nodes | B1 | Identifying odd nodes (or by implication) |
| $48 + 300 = \mathbf{348}$ metres | M1, A1 [3] | For their $48 + 300$ (or their 300); 348 (cao) |
## Part (c)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Odd nodes $A, B, H, J$ | B1 | Identifying odd nodes (or by implication) |
| $AB = 24$; $AH = 37$; $AJ = 48$ | B1 | For distances from $A$ – or from their Dijkstra |
| $HJ = 11$; $BJ = 38$; $BH = 34$ | B1 | For distances $HJ$, $BJ$, $BH$ correct |
| Repeat $AB$ and $HJ = 35$ | M1, M1 | Choosing their least pairing or by implication |
| $300 - 30 = 270$ metres | | Or by implication |
| Shortest distance $= 270 + 35 = \mathbf{305}$ metres | A1 [6] | 305 (cao) |(i) Calculate the shortest distance that the mole must travel if it starts and ends at vertex $A$.\\
(ii) The pipe connecting $B$ to $H$ is removed for repairs. By considering every possible pairing of odd vertices, and showing your working clearly, calculate the shortest distance that the mole must travel to pass along each pipe on this reduced network, starting and finishing at $A$.
\hfill \mbox{\textit{OCR D1 2006 Q6 [16]}}