| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| 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 textbook application of the algorithm. Part (a) requires identifying odd vertices and pairing them optimally, part (b) asks for the route length (total + repeated arcs), and part (c) involves the straightforward extension where starting vertex is fixed. All steps follow the standard algorithm with no novel insight required, making it slightly easier than average. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| AB + DE = 44 + 30 = 74* | M1 | |
| AD + BE = 42 + 35 = 77 | (5) | |
| AE + BD = 39 + 38 = 77 | A3.2.1.0 | |
| Repeat arcs AC, BC and DE | A1 | |
| E.g. ABCADCBEDFGDEGHECA (18 nodes) | B1 | (2) |
| Length: 344 + 74 = 418 | B1ft | |
| One of AB (44), AD (42) or BD (38) will still have to be repeated. | M1 | (3) |
| BD(38) is the shortest | A1 | |
| So start at E and finish at A, route length now is 344 + 38 = 382 | DA1 | |
| 10 marks |
| AB + DE = 44 + 30 = 74* | M1 | |
| AD + BE = 42 + 35 = 77 | | (5) |
| AE + BD = 39 + 38 = 77 | A3.2.1.0 | |
| Repeat arcs AC, BC and DE | A1 | |
| | | |
| E.g. ABCADCBEDFGDEGHECA (18 nodes) | B1 | (2) |
| Length: 344 + 74 = 418 | B1ft | |
| | | |
| One of AB (44), AD (42) or BD (38) will still have to be repeated. | M1 | (3) |
| **BD(38) is the shortest** | A1 | |
| So start at E and finish at A, route length now is 344 + 38 = 382 | DA1 | |
| | | 10 marks |
**Notes for Question 5:**
- a1M1: Three distinct pairings of their four odd nodes
- a1A1: Any one row correct including pairing and total
- a2A1: Any two rows correct including pairing and total
- a3A1: All three rows correct including pairing and total
- a4A1: CAO correct arcs identified AC, BC and DE. Accept ACB or AB via C (check to see if via C appears in working) but **do not accept AB for this mark**
- b1B1: Any correct route (checks: eighteen nodes (or seventeen arcs), the route starts and ends at A, pairings AC, BC and DE appear twice in the route and that every letter (A to H inclusive) appears at least once).
- b2B1ft: correct answer of 418 or 344 + their least out of a choice of at least two totals given in part (a)
- c1M1: Either identifies the need to repeat one pairing which does not include E (could list potential repeats) or identifies the need to repeat BD (or 38).
- c1A1: Identifies the need to repeat one pairing which does not include E **and this is BD (38) because it is the least**. To score the first two marks the candidate must make it clear that they need to repeat **BD because it has the least weight of those pairings that do not include E**.
- c2DA1: correct finishing point (A) and length (382). This mark is dependent on them identifying BD (38) as the repeat.
---5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5b32eb57-c9cd-46ec-a328-12050148bdf7-6_829_1547_257_259}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
\section*{[The total weight of the network is 344 miles]}
Figure 4 represents a railway network. The number on each arc represents the length, in miles, of that section of the railway.
Sophie needs to travel along each section to check that it is in good condition.\\
She must travel along each arc of the network at least once, and wants to find a route of minimum length. She will start and finish at A.
\begin{enumerate}[label=(\alph*)]
\item Use the route inspection algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
\item Write down a possible shortest inspection route, giving its length.
Sophie now decides to start the inspection route at E. The route must still traverse each arc 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 your route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q5 [10]}}