| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Basic Chinese Postman (closed route) |
| Difficulty | Moderate -0.8 This is a straightforward Chinese Postman Problem application requiring identification of odd-degree vertices, pairing them optimally, and adding repeated edges to the total. The network is small (9 vertices), the algorithm is standard D1 content, and part (b) involves simple route inspection rather than novel problem-solving. Easier than average A-level maths questions. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Identify odd vertices in the network | M1 | Must identify all odd-degree vertices |
| Odd vertices are: \(A, C, D, G\) (degree odd) — find minimum weight pairings | M1 | Correct identification of odd vertices |
| Consider pairings: \(AC + DG\), \(AD + CG\), \(AG + CD\) and find shortest paths for each | M1 | All three pairings considered |
| Minimum extra = shortest pairing selected (e.g. \(AD+CG\) via shortest paths) | A1 | Correct minimum pairing with values |
| Optimal route length \(= 118 +\) (extra repeated edges) | A1 | Correct total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Village \(E\) is visited \(2\) times (or state correct number consistent with part (a)) | B1 | Follow through from (a) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Village \(I\) is visited \(3\) times (or state correct number consistent with part (a)) | B1 | Follow through from (a) |
# Question 3:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Identify odd vertices in the network | M1 | Must identify all odd-degree vertices |
| Odd vertices are: $A, C, D, G$ (degree odd) — find minimum weight pairings | M1 | Correct identification of odd vertices |
| Consider pairings: $AC + DG$, $AD + CG$, $AG + CD$ and find shortest paths for each | M1 | All three pairings considered |
| Minimum extra = shortest pairing selected (e.g. $AD+CG$ via shortest paths) | A1 | Correct minimum pairing with values |
| Optimal route length $= 118 +$ (extra repeated edges) | A1 | Correct total |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Village $E$ is visited $2$ times (or state correct number consistent with part (a)) | B1 | Follow through from (a) |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Village $I$ is visited $3$ times (or state correct number consistent with part (a)) | B1 | Follow through from (a) |3 The following network shows the lengths, in miles, of roads connecting nine villages, $A , B , \ldots , I$.
A delivery man lives in village $A$ and is to drive along all the roads at least once before returning to $A$.\\
\includegraphics[max width=\textwidth, alt={}, center]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-06_1072_1027_548_502}
\begin{enumerate}[label=(\alph*)]
\item Find the length of an optimal Chinese postman route around the nine villages, starting and finishing at $A$.
\item For an optimal Chinese postman route corresponding to your answer in part (a), state:
\begin{enumerate}[label=(\roman*)]
\item the number of times village $E$ would be visited;
\item the number of times village $I$ would be visited.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2013 Q3 [7]}}