| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | Specimen |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Effect of adding/removing edge |
| Difficulty | Standard +0.3 This is a standard route inspection problem with a straightforward application of the Chinese Postman algorithm. Part (a) requires identifying odd vertices and pairing them optimally, part (b) asks for the route length (total weight plus repeated edges), and part (c) tests understanding of how adding an edge affects odd-degree vertices. The conceptual demand is low—it's algorithmic execution with minimal problem-solving insight required. Slightly easier than average due to its routine nature. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(BC + EG = 10.4 + 10.1 = 20.5\) smallest | M1 A1 | 1M1: Three pairings of their four odd nodes; 1A1: one row correct |
| \(BE + CG = 8.3 + 16.1 = 24.4\) | A1 | 2A1: two rows correct |
| \(BG + CE = 14.9 + 11.9 = 26.8\) | A1 | 3A1: all correct |
| So repeat tunnels BA, AC and EG | A1 | 5 marks total; 4A1: correct arcs identified |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Any route e.g. ACFGDCABDEGEBA; Length \(= 73.3 +\) their \(20.5 = 93.8\) km | B1, M1 A1 | 3 marks; 1B1: Any correct route (14 nodes); 1M1: \(73.3 +\) ft their least, from a choice of at least two; 1A1: cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| The new tunnel would make C and G even. So only BE would need to be repeated. Extra distance would be \(10 + 8.3 = 18.3 < 20.5\) \([91.6 < 93.8]\). So it would decrease the total distance. | B1, DB1 | 2 marks; 1B1: A correct explanation referring to BE and relevant numbers \((8.3, 12.2, 2.2, 18.3, 81.3, 91.6)\) — may be confused, incomplete or lack conclusion (bod gets B1); 2B1D: A correct, clear explanation all there + conclusion (ft on their numbers) |
# Question 4:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $BC + EG = 10.4 + 10.1 = 20.5$ smallest | M1 A1 | 1M1: Three pairings of their four odd nodes; 1A1: one row correct |
| $BE + CG = 8.3 + 16.1 = 24.4$ | A1 | 2A1: two rows correct |
| $BG + CE = 14.9 + 11.9 = 26.8$ | A1 | 3A1: all correct |
| So repeat tunnels BA, AC and EG | A1 | **5 marks total**; 4A1: correct **arcs** identified |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Any route e.g. ACFGDCABDEGEBA; Length $= 73.3 +$ their $20.5 = 93.8$ km | B1, M1 A1 | **3 marks**; 1B1: Any correct route (14 nodes); 1M1: $73.3 +$ ft their least, from a choice of at least two; 1A1: cao |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| The new tunnel would make C and G even. So only BE would need to be repeated. Extra distance would be $10 + 8.3 = 18.3 < 20.5$ $[91.6 < 93.8]$. So it would decrease the total distance. | B1, DB1 | **2 marks**; 1B1: A correct explanation referring to BE and relevant numbers $(8.3, 12.2, 2.2, 18.3, 81.3, 91.6)$ — may be confused, incomplete or lack conclusion (bod gets B1); 2B1D: A correct, clear explanation all there + conclusion (ft on their numbers) |
**Total: 10 marks**
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5fa867a2-0a3d-4f0b-9f9c-15584f2be5c0-05_879_1068_248_497}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
[The total weight of the network is 73.3 km ]\\
Figure 2 models a network of tunnels that have to be inspected. The number on each arc represents the length, in km , of that tunnel.\\
Malcolm needs to travel through each tunnel at least once and wishes to minimise the length of his inspection route.\\
He must start and finish at A .
\begin{enumerate}[label=(\alph*)]
\item Use the route inspection algorithm to find the tunnels that will need to be traversed twice. You should make your method and working clear.
\item Find a route of minimum length, starting and finishing at A .
State the length of your route.
A new tunnel, CG, is under construction. It will be 10 km long.\\
Malcolm will have to include the new tunnel in his inspection route.
\item What effect will the new tunnel have on the total length of his route?
Justify your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q4 [10]}}