| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2018 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Chinese Postman with different start/end |
| Difficulty | Standard +0.3 This is a standard Chinese Postman problem with specified start/end points. Part (a) requires identifying odd-degree vertices (routine). Part (b) involves pairing odd vertices and finding shortest paths—a mechanical algorithm taught explicitly in D1. Part (c) is straightforward once (b) is complete. While multi-step, it follows a well-rehearsed procedure with no novel insight required, making it slightly easier than average. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Start and finish at G and K (or vice versa) | B1 | CAO (G and K only) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(B(J)G + D(EH)K = 49 + 67 = 116\) | M1 | Three distinct pairings of the correct four nodes (BGDK) |
| \(B(JHE)D + G(H)K = 91 + 48 = 139\) | A1 | Any two rows correct including pairing and total |
| \(B(A)K + G(C)D = 40 + 56 = 96^*\) | A1 | All three rows correct including pairing and total |
| Arcs AB, AK, CG and CD will be traversed twice | A1 | CAO correct arcs clearly stated; must be AB, AK, CG, CD only |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Route: e.g. BABJKAKHJGBCGCDCFGHFDHED | B1 | CAO checks: starts at B finish at D, 24 vertices, AB AK CG CD appear twice |
| Length \(= 601 + 96 = 697\) (m) | B1ft | \(601 +\) their smallest repeat from at least two distinct pairings of correct four nodes |
# Question 5:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Start and finish at G and K (or vice versa) | B1 | CAO (G and K only) |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $B(J)G + D(EH)K = 49 + 67 = 116$ | M1 | Three distinct pairings of the correct four nodes (BGDK) |
| $B(JHE)D + G(H)K = 91 + 48 = 139$ | A1 | Any two rows correct including pairing and total |
| $B(A)K + G(C)D = 40 + 56 = 96^*$ | A1 | All three rows correct including pairing and total |
| Arcs AB, AK, CG and CD will be traversed twice | A1 | CAO correct arcs clearly stated; must be AB, AK, CG, CD **only** |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route: e.g. BABJKAKHJGBCGCDCFGHFDHED | B1 | CAO checks: starts at B finish at D, 24 vertices, AB AK CG CD appear twice |
| Length $= 601 + 96 = 697$ (m) | B1ft | $601 +$ their smallest repeat from at least two distinct pairings of correct four nodes |
---5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e0c89aba-9d2e-469b-8635-d513df0b65a4-06_725_1718_242_169}
\captionsetup{labelformat=empty}
\caption{Figure 6\\[0pt]
[The total weight of the network is 601]}
\end{center}
\end{figure}
Figure 6 represents a network of footpaths in a park. The number on each arc is the length, in metres, of the corresponding footpath. An inspection route of minimum length that traverses each footpath at least once needs to be found.
\begin{enumerate}[label=(\alph*)]
\item Write down the nodes at which the route will start and finish.\\
(1)
It is now decided to start the inspection route at B and finish the inspection route at D . A route of minimum length that traverses each footpath at least once needs to be found.
\item By considering the pairings of all relevant nodes 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.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2018 Q5 [7]}}