| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Apply Prim's Algorithm |
| Difficulty | Moderate -0.3 This is a standard Chinese Postman Problem application from D1, requiring identification of odd vertices and pairing them optimally. Part (a) follows a routine algorithm with clear steps (find odd vertices, find shortest paths between them, add minimum pairing). Part (b) is straightforward once you understand that removing the requirement to return means choosing the two odd vertices from the optimal pairing. While it requires 7 marks worth of working, the method is algorithmic and well-practiced, making it slightly easier than average for A-level. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks |
|---|---|
| m1 A1 / A1 / A1 / (5) |
| Answer | Marks |
|---|---|
| B1^ (e) [2] |
## (a)
Odd vertices B, O, F, H
$BD + FH = 21 + 20 = 41$
$BF + OH = 19 + 20 = 39$ ✓
$BH + OF = 23 + 18 = 41$
Repeat: $BE, EF, DG$ and $GH$
Shortest route $= 12.5 + 39 = 16.4$ km
| m1 A1 / A1 / A1 / (5) |
## (b)
Seek to keep the least pairing - $DF/H$.
Therefore start/finish at $B$ and $H$.
| B1^ (e) [2] |
---\includegraphics{figure_4}
Figure 4 models a network of underground tunnels that have to be inspected. The number on each arc represents the length, in km, of each tunnel.
Joe must travel along each tunnel at least once and the length of his inspection route must be minimised.
The total weight of the network is 125 km.
The inspection route must start and finish at A.
\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. [5]
\end{enumerate}
Given that it is now permitted to start and finish the inspection at two distinct vertices,
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item state which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer. [2]
\end{enumerate}
(Total 7 marks)
\hfill \mbox{\textit{Edexcel D1 2007 Q4 [7]}}