| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Double traversal (both sides of street) |
| Difficulty | Moderate -0.8 Part (a) is a standard textbook route inspection problem requiring the Chinese Postman algorithm with clear scaffolding (6 marks). Part (b) involves recognizing that traversing each edge twice makes all vertices even, requiring only simple observation rather than algorithmic application. This is routine Decision Maths content with no novel problem-solving required. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(CD + FG = 0.7 + 0.6 = 1.3\) | M1, A1 | 3 distinct pairings of their 4 odd nodes; one line correct (condone missing total) |
| \(CF + DG = 0.5 + 0.9 = 1.4\) | A1 | 2 lines correct including totals |
| \(CG + DF = 1.1 + 0.5 = 1.6\) | A1 | All three lines correct including totals |
| Repeat \(CD\) and \(FG\) | ||
| A possible route e.g. \(ACDCFGFDFGEDAEBА\) | A1 | 15 letters, repeat CD and FG, start/finish A, A to G there |
| Length \(= 11 + 1.3 = 12.3\) km | A1ft | \(11+\) their minimum |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (i) Each arc has to be traversed twice | B1 | cao; 'twice' probably the trigger |
| (ii) \(2 \times 11 = 22\) km | B2,0 | 22; 22km |
# Question 3:
## Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $CD + FG = 0.7 + 0.6 = 1.3$ | M1, A1 | 3 distinct pairings of their 4 odd nodes; one line correct (condone missing total) |
| $CF + DG = 0.5 + 0.9 = 1.4$ | A1 | 2 lines correct including totals |
| $CG + DF = 1.1 + 0.5 = 1.6$ | A1 | All three lines correct including totals |
| Repeat $CD$ and $FG$ | | |
| A possible route e.g. $ACDCFGFDFGEDAEBА$ | A1 | 15 letters, repeat CD and FG, start/finish A, A to G there |
| Length $= 11 + 1.3 = 12.3$ km | A1ft | $11+$ their minimum |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| (i) Each arc has to be traversed twice | B1 | cao; 'twice' probably the trigger |
| (ii) $2 \times 11 = 22$ km | B2,0 | 22; 22km |
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-4_755_1132_239_468}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
Figure 4 models a network of roads in a housing estate. The number on each arc represents the length, in km , of the road.
The total weight of the network is 11 km .\\
A council worker needs to travel along each road once to inspect the road surface. He will start and finish at A and wishes to minimise the length of his route.
\begin{enumerate}[label=(\alph*)]
\item Use an appropriate algorithm to find a route for the council worker. You should make your method and working clear. State your route and its length.\\
(6)
A postal worker needs to walk along each road twice, once on each side of the road. She must start and finish at A . The length of her route is to be minimised. You should ignore the width of the road.
\item \begin{enumerate}[label=(\roman*)]
\item Explain how this differs from the standard route inspection problem.\\
(1)
\item Find the length of the shortest route for the postal worker.\\
(2)
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2008 Q3 [9]}}