| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Optimal starting/finishing vertices |
| Difficulty | Moderate -0.3 This is a standard Chinese Postman Problem application with straightforward identification of odd vertices and pairing. Part (a) follows a routine algorithm (find odd vertices, pair them optimally, add repeat edges), and part (b) simply requires recognizing that removing the longest repeat edge by starting/finishing at its endpoints minimizes the route. The question is slightly easier than average because it's algorithmic rather than requiring novel insight, though it does test understanding of the route inspection concept. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Odd vertices C, D, E, G identified | B1 | cao (may be implicit) |
| Three pairings attempted: \(CD+EG=17+19=36\) ← | M1 A1 | Three pairings of their four odd nodes; one row correct |
| \(CE+DG=12+25=37\) | A1 | All correct |
| \(CG+DE=28+13=41\) | ||
| Length \(= 543 + 36 = 579\) (km) | A1ft | \(543 +\) their least \(=\) a number. Condone lack of km |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| CE (12) is the shortest | M1 | Identifies their shortest from a choice of at least 2 rows |
| So repeat CE (12) | A1ft | Indicates their intent to repeat shortest |
| Start and finish at D and G | A1ft | Correct for their least |
# Question 5:
## Part (a)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Odd vertices C, D, E, G identified | B1 | cao (may be implicit) |
| Three pairings attempted: $CD+EG=17+19=36$ ← | M1 A1 | Three pairings of their four odd nodes; one row correct |
| $CE+DG=12+25=37$ | A1 | All correct |
| $CG+DE=28+13=41$ | | |
| Length $= 543 + 36 = 579$ (km) | A1ft | $543 +$ their least $=$ a number. Condone lack of km |
## Part (b)
| Answer/Working | Marks | Guidance |
|---|---|---|
| CE (12) is the shortest | M1 | Identifies their shortest from a choice of at least 2 rows |
| So repeat CE (12) | A1ft | Indicates their intent to repeat shortest |
| Start and finish at D and G | A1ft | Correct for their least |5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{ef029462-ffed-4cdf-87bc-56c8a13d671f-5_806_1211_264_427}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}
(The total weight of the network in Figure 3 is 543 km .)\\
Figure 3 models a network of railway tracks that have to be inspected. The number on each arc is the length, in km , of that section of railway track.\\
Each track must be traversed at least once and the length of the inspection route must be minimised.\\
The inspection route must start and finish at the same vertex.
\begin{enumerate}[label=(\alph*)]
\item Use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear.
It is now permitted to start and finish the inspection at two distinct vertices.
\item State which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2009 Q5 [8]}}