| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Chinese Postman with different start/end |
| Difficulty | Moderate -0.5 This is a standard Chinese Postman problem with straightforward extensions. Part (a) is textbook application of the algorithm (identify odd vertices, find pairings, add repeats). Parts (b) and (c) require minimal adaptation—understanding that different start/end points affect which edges must be repeated. The concepts are routine for D1 students who have practiced route inspection, requiring no novel insight beyond applying learned procedures. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Identify odd nodes: \(B, C, D, F\) | B1 | All four correct |
| Consider pairings: \(BC + DF\), \(BD + CF\), \(BF + CD\) | M1 | Must consider all three pairings |
| \(BC + DF = 7 + 9 = 16\) | A1 | |
| \(BD + CF = (7+7+9) + (9+10) = 42\) or shortest paths used | A1 | |
| \(BF + CD = (7+10) + 28 = 45\) | ||
| Minimum extra \(= 16\) (\(BC\) and \(DF\)) | A1 | |
| Total \(= 150 + 16 = 166\) km | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Odd nodes are \(B, C, D, F\); need to pair \(A\) and \(C\) as start/finish | M1 | Must identify \(A\) and \(C\) need connecting, leaving \(B, D, F\) odd — actually identify which edges repeated |
| Minimum pairing of remaining odd nodes \(B, D, F\) plus \(A\)–\(C\) path considered | ||
| Total \(= 150 + 7 + 9 = 166\) km | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Can start and finish at two different odd nodes, removing best pairing | M1 | Identify that two odd nodes can be start and finish |
| Remove \(BC = 7+\) ... shortest path between best pair of odd nodes | ||
| Total \(= 150 + 9 = 159\) km | A1 | cao (adding DF = 9) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(B\) and \(C\) (or \(C\) and \(B\)) | B1 | Both required |
# Question 5:
## Part (a) - Chinese Postman starting and finishing at A
| Answer | Mark | Guidance |
|--------|------|----------|
| Identify odd nodes: $B, C, D, F$ | B1 | All four correct |
| Consider pairings: $BC + DF$, $BD + CF$, $BF + CD$ | M1 | Must consider all three pairings |
| $BC + DF = 7 + 9 = 16$ | A1 | |
| $BD + CF = (7+7+9) + (9+10) = 42$ or shortest paths used | A1 | |
| $BF + CD = (7+10) + 28 = 45$ | | |
| Minimum extra $= 16$ ($BC$ and $DF$) | A1 | |
| Total $= 150 + 16 = 166$ km | A1 | cao |
## Part (b) - Route from A finishing at C
| Answer | Mark | Guidance |
|--------|------|----------|
| Odd nodes are $B, C, D, F$; need to pair $A$ and $C$ as start/finish | M1 | Must identify $A$ and $C$ need connecting, leaving $B, D, F$ odd — actually identify which edges repeated |
| Minimum pairing of remaining odd nodes $B, D, F$ plus $A$–$C$ path considered | | |
| Total $= 150 + 7 + 9 = 166$ km | A1 | cao |
## Part (c)(i) - Optimal route for Liz (any start, any finish)
| Answer | Mark | Guidance |
|--------|------|----------|
| Can start and finish at two different odd nodes, removing best pairing | M1 | Identify that two odd nodes can be start and finish |
| Remove $BC = 7+$ ... shortest path between best pair of odd nodes | | |
| Total $= 150 + 9 = 159$ km | A1 | cao (adding DF = 9) |
## Part (c)(ii) - Start points for Liz's optimal route
| Answer | Mark | Guidance |
|--------|------|----------|
| $B$ and $C$ (or $C$ and $B$) | B1 | Both required |5 A council is responsible for gritting main roads in a district. The network shows the main roads in the district. The number on each edge shows the length of the road, in kilometres. The gritter starts from the depot located at point $A$, and must drive along all the roads at least once before returning to the depot.\\
\includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-10_1294_923_525_555}
\begin{enumerate}[label=(\alph*)]
\item Find the length of an optimal Chinese postman route around the main roads in the district, starting and finishing at $A$.
\item Zac, a supervisor, wishes to inspect all the roads. He leaves the depot, located at point $A$, and drives along all the roads at least once before finishing at his home, located at point $C$. Find the length of an optimal route for Zac.
\item Liz, a reporter, intends to drive along all the roads at least once in order to report on driving conditions. She can start her journey at any point and can finish her journey at any point.
\begin{enumerate}[label=(\roman*)]
\item Find the length of an optimal route for Liz.
\item State the points from which Liz could start in order to achieve this optimal route.
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-11_2486_1714_221_153}
\end{center}
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2011 Q5 [10]}}