| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Optimal starting/finishing vertices |
| Difficulty | Standard +0.3 This is a standard route inspection (Chinese Postman) problem with straightforward application of the algorithm. Part (a) requires identifying odd vertices and pairing them optimally—routine for D1. Parts (b) and (c) test understanding of semi-Eulerian paths, which is conceptual but not demanding. The question is slightly easier than average A-level since it's algorithmic with clear steps rather than requiring problem-solving insight. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(A(BC)E + H(F)G = 15+13 = 28^*\) | M1 A1 | Three distinct pairings of the correct four odd nodes; one row correct including pairings and totals |
| \(A(BDF)H + E(F)G = 30+7 = 37\) | A1 | Two rows correct including pairings and totals |
| \(A(BDF)G + E(F)H = 21+16 = 37\) | A1 | All three rows correct including pairings and totals |
| Repeat arcs: AB, BC, CE, HF, FG | A1 | The smallest repeat arcs (accept ABCE, HFG but not AE, HG) |
| Length: \(214+28=242\) km | A1ft | Correct answer of 242 or \(214+\) their least |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 4 | B1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| EG (7) is the shortest link between two odd nodes excluding H | M1 | Identifies need to repeat one path of (AE, EG, AG) not including H |
| Repeat EG (7) since this is the shortest path excluding H | A1 | Identifies EG as least and A as finishing point |
| We finish at A | A1 | |
| Length of route \(= 214+7 = 221\) km | A1 | CAO |
# Question 5:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A(BC)E + H(F)G = 15+13 = 28^*$ | M1 A1 | Three distinct pairings of the correct four odd nodes; one row correct including pairings and totals |
| $A(BDF)H + E(F)G = 30+7 = 37$ | A1 | Two rows correct including pairings and totals |
| $A(BDF)G + E(F)H = 21+16 = 37$ | A1 | All three rows correct including pairings and totals |
| Repeat arcs: AB, BC, CE, HF, FG | A1 | The smallest repeat arcs (accept ABCE, HFG but not AE, HG) |
| Length: $214+28=242$ km | A1ft | Correct answer of 242 **or** $214+$ their least |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 4 | B1 | CAO |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| EG (7) is the shortest link between two odd nodes excluding H | M1 | Identifies need to repeat one path of (AE, EG, AG) not including H |
| Repeat EG (7) since this is the shortest path excluding H | A1 | Identifies EG as least **and** A as finishing point |
| We finish at A | A1 | |
| Length of route $= 214+7 = 221$ km | A1 | CAO |
---5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-7_778_1369_239_354}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{center}
\end{figure}
\section*{[The total weight of the network is 214]}
Figure 5 models a network of canals that have to be inspected. The number on each arc represents the length, in km , of the corresponding canal. Priya needs to travel along each canal at least once and wishes to minimise the length of her inspection route.
She must start and finish at A .
\begin{enumerate}[label=(\alph*)]
\item Use the route inspection algorithm to find the length of her route. State the arcs that will need to be traversed twice. You should make your method and working clear.\\
(6)
\item State the number of times that vertex F would appear in Priya's route.\\
(1)
It is now decided to start the inspection route at H . The route must still travel along each canal at least once but may finish at any vertex.
\item Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of the minimum route.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2015 Q5 [10]}}