| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | January |
| Marks | 1 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Explain why Eulerian circuit impossible |
| Difficulty | Easy -1.2 Part (a) requires only stating that an Eulerian circuit needs all vertices of even degree, then checking the diagram shows odd-degree vertices. This is direct recall of a standard theorem with minimal calculation. Part (b) is routine Chinese Postman algorithm application, but the question only asks for part (a) which is straightforward theory. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Odd vertices \((A, D, F, I)\) | E1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(AD + FI = 14 + 14 = 28\) | M1 | |
| \(AF + DI = 14 + 13 = 27\) | A2,1,0 | |
| \(AI + DF = 11 + 17 = 28\) | ||
| \(\therefore\) Repeat \(AF + DI\) | E1 | May be implied |
| Distance \(= 87 + 27 = 114\) | B1 | |
| Route: \(3A, 1B, 2C, 2D, 3E, 2F, 1G, 1H, 2I\) | B1 | 6 17 vertices |
| Total: 7 |
## Question 3(a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Odd vertices $(A, D, F, I)$ | E1 | **1** |
## Question 3(b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $AD + FI = 14 + 14 = 28$ | M1 | |
| $AF + DI = 14 + 13 = 27$ | A2,1,0 | |
| $AI + DF = 11 + 17 = 28$ | | |
| $\therefore$ Repeat $AF + DI$ | E1 | May be implied |
| Distance $= 87 + 27 = 114$ | B1 | |
| Route: $3A, 1B, 2C, 2D, 3E, 2F, 1G, 1H, 2I$ | B1 | **6** 17 vertices |
| **Total: 7** | | |
---3 A local council is responsible for gritting roads.
The diagram shows the length, in miles, of the roads that have to be gritted.\\
\includegraphics[max width=\textwidth, alt={}, center]{76bccb26-f2ec-4798-bb6b-89c922f9651a-03_671_686_488_669}
Total length $= 87$ miles
The gritter is based at $A$, and must travel along all the roads, at least once, before returning to $A$.
\begin{enumerate}[label=(\alph*)]
\item Explain why it is not possible to start from $A$ and, by travelling along each road only once, return to $A$.
\item Find an optimal 'Chinese postman' route around the network, starting and finishing at $A$. State the length of your route.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2005 Q3 [1]}}