| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Explain why Eulerian circuit impossible |
| Difficulty | Moderate -0.3 This is a standard Chinese Postman Problem application from D1, requiring identification of odd-degree vertices (part a), pairing them optimally and adding repeat edges (part b), and counting vertex occurrences (part c). While it involves multiple steps, it follows a well-defined algorithm taught explicitly in the specification with no novel problem-solving required, making it slightly easier than average. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.04e Route inspection: Chinese postman, pairing odd nodes |
Norris delivers newspapers to houses on an estate. The network shows the streets on the estate. The number on each edge shows the length of the street, in metres.
Norris starts from the newsagents located at vertex $A$, and he must walk along all the streets at least once before returning to the newsagents.
\includegraphics{figure_5}
The total length of the streets is 1215 metres.
\begin{enumerate}[label=(\alph*)]
\item Give a reason why it is not possible to start at $A$, walk along each street once only, and return to $A$. [1]
\item Find the length of an optimal Chinese postman route around the estate, starting and finishing at $A$. [5]
\item For an optimal Chinese postman route, state:
\begin{enumerate}[label=(\roman*)]
\item the number of times that the vertex $F$ would occur; [1]
\item the number of times that the vertex $H$ would occur. [1]
\end{enumerate}
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2011 Q5 [8]}}