| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Count vertex occurrences in route |
| Difficulty | Standard +0.3 This is a standard Chinese Postman Problem application requiring identification of odd-degree vertices, pairing them optimally, and counting vertex occurrences. While it involves multiple steps, the algorithm is routine for D1 students and the vertex counting in part (b) is straightforward once the repeated edges are identified. Slightly above average due to the network size and need for systematic working. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Identify odd vertices | B1 | Vertices with odd degree must be identified |
| List pairings of odd vertices and find shortest path for each pairing | M1 | Must consider all possible pairings |
| Correct shortest path values stated for pairings | A1 | |
| Identify minimum extra and add to 224 | M1 | |
| Correct optimal route length = \(224 + \text{repeat}\) minutes | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct number of times \(J\) appears stated (e.g. 3 times) | B1 | Follow through from part (a) |
## Question 4:
### Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| Identify odd vertices | B1 | Vertices with odd degree must be identified |
| List pairings of odd vertices and find shortest path for each pairing | M1 | Must consider all possible pairings |
| Correct shortest path values stated for pairings | A1 | |
| Identify minimum extra and add to 224 | M1 | |
| Correct optimal route length = $224 + \text{repeat}$ minutes | A1 | cao |
### Part (b):
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct number of times $J$ appears stated (e.g. 3 times) | B1 | Follow through from part (a) |
---4 The following network shows the times, in minutes, taken by a policeman to walk along roads connecting 12 places, $A , B , \ldots , L$, on his beat. Each day, the policeman has to walk along each road at least once, starting and finishing at $A$.\\
\includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-08_1141_1313_461_360}
The total of all the times in the network is 224 minutes.
\begin{enumerate}[label=(\alph*)]
\item Find the length of an optimal Chinese postman route for the policeman.
\item State the number of times that the vertex $J$ would appear in a route corresponding to the length found in part (a).
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2012 Q4 [6]}}