| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Chinese Postman with flexible endpoints |
| Difficulty | Standard +0.3 This is a straightforward application of the Chinese Postman algorithm with standard variations. Part (a) is textbook CPP, part (b) requires finding shortest paths between odd vertices with fixed endpoints (routine), and part (c) involves recognizing that an optimal route between two odd vertices requires no repeats. The network analysis and calculations are mechanical with no novel insights required. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
## Question 5
(a) Find the length of an optimal Chinese postman route for Tony. (5 marks)
- M1: Identification of odd-degree vertices
- M1: Recognition that route must traverse all edges at least once
- M1: Calculation of shortest paths between odd-degree vertices
- M1: Identification of minimum weight matching of odd-degree vertices
- A1: Correct total route length stated
(b) Colin also wishes to distribute some leaflets. He starts from his house at H, walks along all the streets at least once, before finishing at the restaurant at B. Colin wishes to walk the minimum distance. Find the length of an optimal route for Colin. (1 mark)
- A1: Correct distance calculated (sum of all streets plus shortest path from H to B, accounting for the fact that not all edges need to be traversed twice)
(c) David also walks along all the streets at least once. He can start at any vertex and finish at any vertex. David also wishes to walk the minimum distance.
(i) Find the length of an optimal route for David. (1 mark)
- A1: Correct minimum distance (sum of all streets only, as Eulerian path exists between two odd-degree vertices)
(ii) State the vertices from which David could start in order to achieve this optimal route. (1 mark)
- A1: Both odd-degree vertices correctly identified5 The network below shows some streets in a town. The number on each edge shows the length of that street, in metres.
Leaflets are to be distributed by a restaurant owner, Tony, from his restaurant located at vertex $B$. Tony must start from his restaurant, walk along all the streets at least once, before returning to his restaurant.\\
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-10_643_1353_625_340}
The total length of the streets is 2430 metres.
\begin{enumerate}[label=(\alph*)]
\item Find the length of an optimal Chinese postman route for Tony.
\item Colin also wishes to distribute some leaflets. He starts from his house at $H$, walks along all the streets at least once, before finishing at the restaurant at $B$.
Colin wishes to walk the minimum distance. Find the length of an optimal route for Colin.
\item David also walks along all the streets at least once. He can start at any vertex and finish at any vertex. David also wishes to walk the minimum distance.
\begin{enumerate}[label=(\roman*)]
\item Find the length of an optimal route for David.
\item State the vertices from which David could start in order to achieve this optimal route.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2012 Q5 [8]}}