| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Optimal starting/finishing vertices |
| Difficulty | Moderate -0.3 This is a standard route inspection (Chinese Postman) problem with textbook application of the algorithm. Part (a) requires identifying odd vertices, finding minimum pairings, and adding repeated edges—routine for D1 students who've practiced the method. Part (b) is a direct conceptual follow-up about semi-Eulerian paths. The 5+2 mark allocation and explicit method prompt indicate this is a procedural question testing algorithm execution rather than problem-solving insight, making it slightly easier than average A-level difficulty. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| \(AC + DF = 8 + 9 = 17\) | M1, A1 | |
| \(BD + CF = 15 + 16 = 31\) | M1, A1∧ | |
| \(AF + CD = 13 + 7 = 20\) | ||
| Length \(= 77 + 17 = 94 \text{ km}\) | B2, 1, 0 |
| Answer | Marks | Guidance |
|---|---|---|
| Shortest arc is \(CD\) (7), so use A and F as end points | ||
| @3ym) 3 pairs of 4 odd vertices (different) ACDF | A1 | |
| A1 | 2 pairs + "total" correct | |
| A1 | All 3 pairs + total correct: 17, 31, 20 | |
| M1 | \(77 + \underline{\text{their shortest}}\) or plausible list | |
| A1∧ | \(CAO + \text{km}\) | |
| B2 | CD identified as needed to be repeated; A+F stated as end points | |
| B1 | either CD identified, unnamed to be repeated, or A+F stated as end points. 'bad set B1' or plausible smallest out of at least two |
## Part (a)
| $AC + DF = 8 + 9 = 17$ | M1, A1 | |
| $BD + CF = 15 + 16 = 31$ | | M1, A1∧ |
| $AF + CD = 13 + 7 = 20$ | | |
| Length $= 77 + 17 = 94 \text{ km}$ | | B2, 1, 0 |
## Part (b)
| Shortest arc is $CD$ (7), so use A and F as end points | | |
| **@3ym)** 3 pairs of 4 odd vertices (different) ACDF | A1 | |
| | A1 | 2 pairs + "total" correct |
| | A1 | All 3 pairs + total correct: 17, 31, 20 |
| | M1 | $77 + \underline{\text{their shortest}}$ or plausible list |
| | A1∧ | $CAO + \text{km}$ |
| **B2** | CD identified as needed to be repeated; A+F stated as end points | | **Smallest or** |
| **B1** | either CD identified, unnamed to be repeated, or A+F stated as end points. 'bad set B1' or plausible smallest out of at least two | |
---\includegraphics{figure_2}
Figure 2 models a network of roads which need to be inspected to assess if they need to be resurfaced. The number on each arc represents the length, in km, of that road.
Each road must be traversed at least once and the length of the inspection route must be minimised.
\begin{enumerate}[label=(\alph*)]
\item Starting and finishing at $A$, solve this route inspection problem. You should make your method and working clear. State the length of the shortest route.
(The weight of the network is 77 km.) [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 you should choose to minimise the length of the route. Give a reason for your answer. [2]
\end{enumerate}
(Total 7 marks)
\hfill \mbox{\textit{Edexcel D1 2005 Q3 [7]}}