| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Basic Chinese Postman (closed route) |
| Difficulty | Moderate -0.3 This is a standard textbook application of the route inspection algorithm with straightforward steps: prove the handshaking lemma, identify odd vertices, pair them optimally, and calculate the route length. The theory part (a) is a well-known result, and parts (b)-(c) follow the algorithm mechanically with no novel problem-solving required. Slightly easier than average due to being a routine algorithmic procedure. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks |
|---|---|
| Each edge contributes 2 to the sum of degrees, hence this sum must be even. Therefore there must be an even (or zero) number of vertices of odd degree. Hence there cannot be an odd number of vertices of odd degree | B2, 1, 0 (2) |
| Answer | Marks |
|---|---|
| \(CD + FH = 200 + 220 = 420\) / \(CF + DH = 180 + 280 = 560\) / \(CM + DF = 400 + 160 = 560\) / repeat CA, AD and FH | M1, A1, A1 (4) |
| Answer | Marks |
|---|---|
| length = \(4180 + 420/ = 4600\) m | BW (1), [7] |
## 5(a)
| Each edge contributes 2 to the sum of degrees, hence this sum must be even. Therefore there must be an even (or zero) number of vertices of odd degree. Hence there cannot be an odd number of vertices of odd degree | B2, 1, 0 (2) |
## 5(b)
| $CD + FH = 200 + 220 = 420$ / $CF + DH = 180 + 280 = 560$ / $CM + DF = 400 + 160 = 560$ / repeat CA, AD and FH | M1, A1, A1 (4) |
## 5(c)
| length = $4180 + 420/ = 4600$ m | BW (1), [7] |\begin{enumerate}[label=(\alph*)]
\item Explain why a network cannot have an odd number of vertices of odd degree. (2)
\end{enumerate}
\includegraphics{figure_4}
Figure 4 shows a network of paths in a public park. The number on each arc represents the length of that path in metres. Hamish needs to walk along each path at least once to check the paths for frost damage starting and finishing at $A$. He wishes to minimise the total distance he walks.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Use the route inspection algorithm to find which paths, if any, need to be traversed twice. (4)
\item Find the length of Hamish's route.
[The total weight of the network in Figure 4 is 4180 m.] (1)
\end{enumerate}
(Total 7 marks)
\hfill \mbox{\textit{Edexcel D1 2007 Q5}}