| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2004 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Write explicit optimal route |
| Difficulty | Standard +0.3 This is a standard route inspection (Chinese Postman) problem requiring application of a well-defined algorithm to find odd vertices, pair them optimally, and construct an Eulerian path. Part (a) follows textbook procedure with minimal problem-solving, while part (b) requires recognizing that changing start/end points from G-G to D-G reduces required repeats. The question is slightly easier than average A-level as it's algorithmic application rather than proof or novel insight, though the two-part structure and need to identify optimal pairings adds some complexity. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
\includegraphics{figure_2}
An engineer needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Fig. 2. The number on each arc represents the length of that road in km. To check all the roads, he needs to travel along each road at least once. He wishes to minimise the total distance travelled.
The engineer's office is at $G$, so he starts and ends his journey at $G$.
\begin{enumerate}[label=(\alph*)]
\item Use an appropriate algorithm to find a route for the engineer to follow. State your route and its length. [6]
\end{enumerate}
The engineer lives at $D$. He believes he can reduce the distance travelled by starting from home and inspecting all the roads on the way to his office at $G$.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item State whether the engineer is correct in his belief. If so, calculate how much shorter his new route is. If not, explain why not. [3]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2004 Q4 [9]}}