| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2021 |
| Session | January |
| Marks | 17 |
| 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 D1 Chinese Postman problem with straightforward application of algorithms. Part (a) is routine Dijkstra's, parts (b-d) require identifying odd vertices and pairing them (textbook procedure), and parts (e-f) apply the same method with different start/end points. All steps follow well-rehearsed algorithms with no novel insight required, making it slightly easier than average. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Correct application of Dijkstra's algorithm (larger value replaced by smaller in working value boxes at C, F, K, J, or H) | M1 | At least two working value boxes updated correctly |
| All values at A, B, C, D, E correct with working values in correct order | A1 | If working value of 45 appears at E it must appear after the 36 |
| All values at F, G, K correct with working values in correct order | A1 | F, G, K must be labelled in that order, F labelled after A,B,C,D,E |
| All values at J, H correct on follow through with working values in correct order | A1ft | Follow through from candidate's values |
| Shortest path: A B D G K H | A1 | CAO |
| Length: 68 (miles) | A1ft | Follow through on final value at H only |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Route from F to K via A: F E C B A B D G K | B1 | CAO |
| Length: \(41 + 62 = 103\) (miles) | B1ft | Follow through their final value at F + their final value at K, or 103 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(AJ + CE = 67 + 16 = 83\) | M1 A1 | Correct three distinct pairings of the correct four odd nodes A, C, E, J; any row correct including pairing and total |
| \(AC + EJ = 20 + 32 = 52\) | A1 | Any two rows correct including pairings and totals |
| \(AE + CJ = 36 + 48 = 84\) | A1 | All three rows correct including pairings and totals |
| Repeated arcs: AB, BC, EF, FK, JK | A1 | CAO — must be stated as these arcs, not just in working |
| Length: \(253 + 52 = 305\) (miles) | A1ft | Follow through their smallest pairing total \(+ 253\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Vertex F: 4 times | B1 | CAO (4 only) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| (Start at D and) finish at C | B1 | CAO (C) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Difference \(= 305 - (253 + 10) = 42\) (miles) | B1 | CAO (42) |
# Question 5:
## Part (a)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Correct application of Dijkstra's algorithm (larger value replaced by smaller in working value boxes at C, F, K, J, or H) | M1 | At least two working value boxes updated correctly |
| All values at A, B, C, D, E correct with working values in correct order | A1 | If working value of 45 appears at E it must appear after the 36 |
| All values at F, G, K correct with working values in correct order | A1 | F, G, K must be labelled in that order, F labelled after A,B,C,D,E |
| All values at J, H correct on follow through with working values in correct order | A1ft | Follow through from candidate's values |
| Shortest path: A B D G K H | A1 | CAO |
| Length: 68 (miles) | A1ft | Follow through on final value at H only |
## Part (b)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Route from F to K via A: F E C B A B D G K | B1 | CAO |
| Length: $41 + 62 = 103$ (miles) | B1ft | Follow through their final value at F + their final value at K, or 103 |
## Part (c)
| Answer/Working | Mark | Guidance |
|---|---|---|
| $AJ + CE = 67 + 16 = 83$ | M1 A1 | Correct three distinct pairings of the correct four odd nodes A, C, E, J; any row correct including pairing and total |
| $AC + EJ = 20 + 32 = 52$ | A1 | Any two rows correct including pairings and totals |
| $AE + CJ = 36 + 48 = 84$ | A1 | All three rows correct including pairings and totals |
| Repeated arcs: AB, BC, EF, FK, JK | A1 | CAO — must be stated as these arcs, not just in working |
| Length: $253 + 52 = 305$ (miles) | A1ft | Follow through their smallest pairing total $+ 253$ |
## Part (d)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Vertex F: 4 times | B1 | CAO (4 only) |
## Part (e)
| Answer/Working | Mark | Guidance |
|---|---|---|
| (Start at D and) finish at C | B1 | CAO (C) |
## Part (f)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Difference $= 305 - (253 + 10) = 42$ (miles) | B1 | CAO (42) |
---5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{48e785c0-7de5-450f-862c-4dd4d169adf9-06_952_1511_230_278}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
[The total weight of the network is 253]
Figure 1 represents a network of roads between 10 cities, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in miles, of the corresponding road.
One day, Mabintou wishes to travel from A to H. She wishes to minimise the distance she travels.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest path from A to H . State your path and its length.
On another day, Mabintou wishes to travel from F to K via A.
\item Find a route of minimum length from F to K via A and state its length.
The roads between the cities need to be inspected. James must travel along each road at least once. He wishes to minimise the length of his inspection route. James will start his inspection route at A and finish at J.
\item By considering the pairings of all relevant nodes, find the length of James' route. State the arcs that will need to be traversed twice. You must make your method and working clear.\\
(6)
\item State the number of times that James will pass through F.
It is now decided to start the inspection route at D. James must minimise the length of his route. He must travel along each road at least once but may finish at any vertex.
\item State the vertex where the new inspection route will finish.
\item Calculate the difference between the lengths of the two inspection routes.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2021 Q5 [17]}}