| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Count vertex occurrences in route |
| Difficulty | Moderate -0.5 This is a straightforward application of the Chinese Postman algorithm with standard follow-up questions about vertex traversal. Part (a) requires identifying odd vertices and finding minimum pairings (routine for D1), while part (b) simply asks students to count vertex occurrences in the optimal route—a mechanical task once the route is determined. The question is slightly easier than average because it's a textbook application with no novel problem-solving required. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Mark | Guidance |
| Identify odd vertices | M1 | Must identify correct odd degree vertices |
| Odd vertices are: \(B, C, E, F\) (degrees 3, 3, 3, 3) | A1 | |
| Consider pairings: \(BC+EF = 50+70+70 = 190\); \(BE+CF = 130+90+100+160=...\); \(BF+CE=...\) | M1 | At least two pairings attempted |
| Minimum pairing: \(BC + EF = 70+70 = 140\) (shortest paths) | A1 | |
| Optimal route length \(= 1400 + 140 = 1540\) m | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Mark | Guidance |
| 3 times | B1 | ft from (a) |
| Answer | Marks | Guidance |
|---|---|---|
| Working | Mark | Guidance |
| 2 times | B1 | ft from (a) |
## Question 5:
**(a)** Chinese Postman route length
| Working | Mark | Guidance |
|---------|------|----------|
| Identify odd vertices | M1 | Must identify correct odd degree vertices |
| Odd vertices are: $B, C, E, F$ (degrees 3, 3, 3, 3) | A1 | |
| Consider pairings: $BC+EF = 50+70+70 = 190$; $BE+CF = 130+90+100+160=...$; $BF+CE=...$ | M1 | At least two pairings attempted |
| Minimum pairing: $BC + EF = 70+70 = 140$ (shortest paths) | A1 | |
| Optimal route length $= 1400 + 140 = 1540$ m | A1 | cao |
**(b)(i)** Number of times mower passes through C
| Working | Mark | Guidance |
|---------|------|----------|
| 3 times | B1 | ft from (a) |
**(b)(ii)** Number of times mower passes through D
| Working | Mark | Guidance |
|---------|------|----------|
| 2 times | B1 | ft from (a) |5 The network shows the paths mown through a wildflower meadow so that visitors can use these paths to enjoy the flowers. The lengths of the paths are shown in metres.\\
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-10_1097_1603_413_214}
The total length of all the paths is 1400 m .\\
The mower is kept in a shed at $A$. The groundskeeper must mow all the paths and return the mower to its shed.
\begin{enumerate}[label=(\alph*)]
\item Find the length of an optimal Chinese postman route starting and finishing at $A$.
\item State the number of times that the mower, following the optimal route, will pass through:
\begin{enumerate}[label=(\roman*)]
\item $C$;
\item $D$.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2015 Q5 [7]}}