| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Count vertex occurrences in route |
| Difficulty | Moderate -0.3 This is a standard Chinese Postman Problem application requiring identification of odd vertices, pairing them optimally, and basic route analysis. While it involves multiple parts, each step follows a well-defined algorithm taught in D1 with minimal problem-solving insight needed—slightly easier than average due to the mechanical nature of the CPP algorithm. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Identify odd vertices: \(B, C, D, E, F, G, H\) ... need to find odd vertices | M1 | Must identify odd degree vertices |
| Odd vertices are \(C, E, G, H\) (degree 3 each) | B1 | Correct identification of all odd vertices |
| Pairings: \(CE + GH\), \(CG + EH\), \(CH + EG\) | M1 | Consider correct pairings of odd vertices |
| \(CE = 0.5 + 14 = 14.5\), \(GH = 4\); total \(= 18.5\) | ||
| \(CG = 0.5 + 3.5 + 4.5 + 4 = ?\) or by inspection | ||
| \(EG = 3.5 + 4 + 4.5 + 4 = ?\) or \(6 + 3.5\); \(CH = 2 + 4 = 6\) | ||
| Minimum repeat = \(CE + GH = 14.5 + 4 = 18.5\)... select minimum pairing | A1 | Correct minimum pairing identified |
| Optimal route \(= 79.5 + \) (minimum repeat) | M1 | Adding repeat to total |
| \(= 79.5 + \) minimum \(= \) answer | A1 | Correct final answer |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (i) Vertex \(F\) occurs 2 times | B1 | ft from their route |
| (ii) Vertex \(D\) occurs 2 times | B1 | ft from their route |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (i) For an open traverse, only need to pair up remaining odd vertices minus two (start/end at odd vertices) | M1 | Correct method — remove best pair of odd vertices |
| Remove pair \(CE\) (or whichever gives minimum); repeat \(= GH = 4\) | A1 | Correct identification |
| Optimal route for Toto \(= 79.5 + 4 = 83.5\) minutes | A1 | Correct answer |
| (ii) Toto could start at \(C\) and finish at \(E\) (or vice versa), or start at \(G\) and finish at \(H\) (or vice versa) | B1 | Both pairs stated (allow either order within pair) |
# Question 4:
## Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Identify odd vertices: $B, C, D, E, F, G, H$ ... need to find odd vertices | M1 | Must identify odd degree vertices |
| Odd vertices are $C, E, G, H$ (degree 3 each) | B1 | Correct identification of all odd vertices |
| Pairings: $CE + GH$, $CG + EH$, $CH + EG$ | M1 | Consider correct pairings of odd vertices |
| $CE = 0.5 + 14 = 14.5$, $GH = 4$; total $= 18.5$ | | |
| $CG = 0.5 + 3.5 + 4.5 + 4 = ?$ or by inspection | | |
| $EG = 3.5 + 4 + 4.5 + 4 = ?$ or $6 + 3.5$; $CH = 2 + 4 = 6$ | | |
| Minimum repeat = $CE + GH = 14.5 + 4 = 18.5$... select minimum pairing | A1 | Correct minimum pairing identified |
| Optimal route $= 79.5 + $ (minimum repeat) | M1 | Adding repeat to total |
| $= 79.5 + $ minimum $= $ answer | A1 | Correct final answer |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| **(i)** Vertex $F$ occurs **2** times | B1 | ft from their route |
| **(ii)** Vertex $D$ occurs **2** times | B1 | ft from their route |
## Part (c):
| Answer | Marks | Guidance |
|--------|-------|----------|
| **(i)** For an open traverse, only need to pair up remaining odd vertices minus two (start/end at odd vertices) | M1 | Correct method — remove best pair of odd vertices |
| Remove pair $CE$ (or whichever gives minimum); repeat $= GH = 4$ | A1 | Correct identification |
| Optimal route for Toto $= 79.5 + 4 = 83.5$ minutes | A1 | Correct answer |
| **(ii)** Toto could start at $C$ and finish at $E$ (or vice versa), or start at $G$ and finish at $H$ (or vice versa) | B1 | Both pairs stated (allow either order within pair) |4 Paulo sells vegetables from his van. He drives around the streets of a small village. The network shows the streets in the village. The number on each edge shows the time, in minutes, to drive along that street.
Paulo starts from his house located at vertex $A$ and drives along all the streets at least once before returning to his house.\\
\includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-10_1518_1605_598_198}
The total of all the times in the diagram is 79.5 minutes.
\begin{enumerate}[label=(\alph*)]
\item Find the length of an optimal Chinese postman route around the village, starting and finishing at $A$. (Shortest routes between vertices may be found by inspection.)
\item For an optimal Chinese postman route, state:
\begin{enumerate}[label=(\roman*)]
\item the number of times the vertex $F$ would occur;
\item the number of times the vertex $D$ would occur.
\end{enumerate}\item Toto is standing for the position of Mayor in the local elections. He intends to travel along all the roads at least once. He can start his journey at any vertex and can finish his journey at any vertex.
\begin{enumerate}[label=(\roman*)]
\item Find the length of an optimal route for Toto.\\[0pt]
\item State the vertices from which Toto could start in order to achieve this optimal route. [3 marks]
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2014 Q4 [10]}}