| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Optimal starting/finishing vertices |
| Difficulty | Moderate -0.8 This is a straightforward application of the route inspection (Chinese Postman) algorithm with standard steps: identify odd vertices, find pairings, and determine repeated arcs. Part (c) extends to the semi-Eulerian case but requires only basic reasoning. The algorithm is mechanical with minimal problem-solving required, and the total network weight is given, making this easier than average. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks |
|---|---|
| \[AC + EG = 44 + 35 = 79\] | m1 A1 |
| \[AE + CG = 41 + 36 = 77\] | A1 |
| Answer | Marks |
|---|---|
| Repeat \(A D, DE, CF\) and \(FG\) | A1(4) |
| (b) Length \(= 294 + 77 = 471\) km | B1(1) |
| (c) Since \(EG\) is the smallest chord to repeat this hence start and finish at \(A\) and \(C\) | m1 A1(2) |
(a)
$$AC + EG = 44 + 35 = 79$$ | m1 A1
$$AE + CG = 41 + 36 = 77$$ | A1
$$AG + CE = 36 + 45 = 81$$
Repeat $A D, DE, CF$ and $FG$ | A1(4)
(b) Length $= 294 + 77 = 471$ km | B1(1)
(c) Since $EG$ is the smallest chord to repeat this hence start and finish at $A$ and $C$ | m1 A1(2)
---\includegraphics{figure_2}
Figure 2 shows the network of pipes represented by arcs. The length of each pipe, in kilometres, is shown by the number on each arc. The network is to be inspected for leakages, using the shortest route and starting and finishing at A.
\begin{enumerate}[label=(\alph*)]
\item Use the route inspection algorithm to find which arcs, if any, need to be traversed twice. [4]
\item State the length of the minimum route. [The total weight of the network is 394 km.] [1]
\end{enumerate}
It is now permitted to start and finish the inspection at two distinct vertices.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item State, with a reason, which two vertices should be chosen to minimise the length of the new route. [2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2006 Q3 [7]}}