| 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 | Write explicit optimal route |
| Difficulty | Standard +0.3 This is a standard route inspection algorithm question requiring identification of odd vertices, pairing them optimally, and writing out a route. While it involves multiple steps (finding odd vertices, calculating pairings, determining repeated arcs), the algorithm is mechanical and well-practiced in D1. Part (c) adds slight complexity by requiring understanding that removing the longest repeated arc gives the optimal open route, but this is a standard extension. Slightly easier than average due to the algorithmic nature requiring minimal problem-solving insight. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
**Question 5 Notes:**
- 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 specified AB, BF and GH. Accept ABF or AF via B (check to see if via B appears in working) but do not accept AF for this mark
- b1B1: Any correct route (checks: 17 nodes, the route starts and ends at A, pairings AB, BF and GH appear twice in the route and every letter from A to H (inclusive) appears at least once)
- b2B1 ft: correct answer of 227 or 181 + their least out of a choice of at least two totals given in part (a)
- c1M1: Identifies need to repeat one pairing (maybe implicit) and 15 (or either AF or FH) specifically identified as the least
- c1A1: Repeat (either AF or FH) identified clearly
- c2A1: G and either A or H identified as start and finish5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-06_712_1520_246_267}
\captionsetup{labelformat=empty}
\caption{Figure 4\\[0pt]
[The total weight of the network is 181 miles]}
\end{center}
\end{figure}
Figure 4 represents a network of power cables that have to be inspected. The number on each arc represents the length, in km , of that cable.
A route of minimum length that traverses each cable at least once and starts and finishes at A needs to be found.
\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.
It is now decided to start and finish the inspection route at two distinct vertices. The route must still traverse each cable at least once.
\item Determine possible starting and finishing points so that the length of the route is minimised. You must give reasons for your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q5 [10]}}