| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2004 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Basic Chinese Postman (closed route) |
| Difficulty | Moderate -0.8 This is a standard textbook application of the route inspection (Chinese Postman) algorithm with straightforward steps: identify odd vertices, pair them optimally, and calculate the route length. Part (e) extends to semi-Eulerian paths but remains algorithmic. The question requires minimal problem-solving insight—just methodical application of a well-defined procedure taught explicitly in D1. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
\includegraphics{figure_2}
\begin{enumerate}[label=(\alph*)]
\item Describe a practical problem that could be modelled using the network in Fig. 2 and solved using the route inspection algorithm. [1]
\item Use the route inspection algorithm to find which paths, if any, need to be traversed twice. [4]
\item State whether your answer to part (b) is unique. Give a reason for your answer. [1]
\item Find the length of the shortest inspection route that traverses each arc at least once and starts and finishes at the same vertex. [1]
\end{enumerate}
Given that it is permitted to start and finish the inspection at two distinct vertices,
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{4}
\item find which two vertices should be chosen to minimise the length of the route. Give a reason for your answer. [2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2004 Q3 [9]}}