| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | January |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Combined Dijkstra and route inspection |
| Difficulty | Challenging +1.2 This is a multi-part question combining Dijkstra's algorithm and route inspection (Chinese Postman Problem), both standard D1 topics. Part (a) is routine application of Dijkstra. Parts (b)-(c) require identifying odd vertices and pairing them optimally—a standard textbook procedure. Part (d) adds a twist by removing edges and considering semi-Eulerian paths, requiring slightly more insight but still following algorithmic procedures. The question is longer and more involved than average, pushing it above baseline difficulty, but doesn't require novel problem-solving approaches. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Network diagram with all values correct | M1 A1 (ABDC) A1(GFH) A1ft (EJ) | |
| Shortest route: ABCFEJ Length: 22 (metres) | A1 A1ft (6) | |
| AE + FJ = 15 + 11 = 26 AF + EJ = 11 + 7 = 18* AJ + EF = 22 + 4 = 26 Arcs AB, BC, CF, EJ will be traversed twice | M1 A1ft A1ft A1 (5) | |
| Route: e.g. ABADGHDFHJEFCFCBCA Length: 100 + 18 = 118 | B1 B1ft (2) | |
| Start at E, finish at J (or vice versa) or start at C, finish at J (or vice-versa) Length: 100 – 3 – 4 + 4 = 97 (metres) | M1 A1 B1 (3) | |
| 16 marks |
| Answer | Marks | Guidance |
|--------|-------|----------|
| Network diagram with all values correct | M1 A1 (ABDC) A1(GFH) A1ft (EJ) | |
| Shortest route: ABCFEJ Length: 22 (metres) | A1 A1ft (6) | |
| AE + FJ = 15 + 11 = 26 AF + EJ = 11 + 7 = 18* AJ + EF = 22 + 4 = 26 Arcs AB, BC, CF, EJ will be traversed twice | M1 A1ft A1ft A1 (5) | |
| Route: e.g. ABADGHDFHJEFCFCBCA Length: 100 + 18 = 118 | B1 B1ft (2) | |
| Start at E, finish at J (or vice versa) or start at C, finish at J (or vice-versa) Length: 100 – 3 – 4 + 4 = 97 (metres) | M1 A1 B1 (3) | |
| | 16 marks | |
**Notes for Question 4:**
- a1M1: A larger value replaced by a smaller value at least once in the working values at either C or E or F or H or J.
- a1A1: All values in A, B, C and D correct and the working values in the correct order, including order of labelling. Condone lack of 0 in A's working value.
- a2A1: All values in F, G and H correct and the working values in the correct order. Penalise order of labelling only once per question. Condone an additional working value at H of 19 after the 13.
- a3A1ft: All values in E and J correct on the follow through and the working values in the correct order. Penalise order of labelling only once per question.
- a4A1: CAO (ABCFEJ) for the route.
- a5A1ft: Follow through on their final value at J – if their answer is not 22 follow through their final value at J (condone lack of units).
- b1M1: Three pairings of the correct four odd nodes.
- b1A1ft: One row correct including pairing and total (the ft on the first three A marks in (b) is for using their final values at E, F and J from (a) for the lengths of AE, AF and AJ only).
- b2A1ft: Two rows correct including pairings and totals.
- b3A1: All three rows correct including pairings and totals.
- b4A1: The smallest repeat arcs AB, BC, CF and EJ clearly stated. Accept ABCF, EJ but not AF.
- c1B1: Any correct route (checks: 20 nodes, starting and finishing at A, pairings AB, BC, CF, EJ appear twice in the route and that A, C and F appear three times, B, D, E, H and J appear twice and G appears once).
- c2B1ft: Correct answer of 118 or 100 + their least out of a choice of at least two totals given in (b).
- d1M1: Any consideration/mention of all of the odd nodes (C, E, F and J) or consideration/mention of all the odd pairings (CE, CF, CJ, EF, EJ, FJ) or consideration/mention of arcs EF and CF (and no others) having a weight of 4 or listing one correct starting and finishing point (must be clear).
- d1A1: Both combinations of starting and finishing points correct (E and J + C and J) and no others.
- d1B1: CAO (97).
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{00abfcc0-63b3-4784-a4b5-06aba234068c-5_889_1591_258_239}
\captionsetup{labelformat=empty}
\caption{Figure 3\\[0pt]
[The total weight of the network is 100]}
\end{center}
\end{figure}
Figure 3 represents a network of pipes in a building. The number on each arc represents the length, in metres, of the corresponding pipe.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest path from A to J . State your path and its length.
On a particular day Kim needs to check each pipe. A route of minimum length, which traverses each pipe at least once and starts and finishes at A, needs to be found.
\item Use an appropriate 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 route, giving its length.
All the pipes directly attached to B are removed. Kim needs to check all the remaining pipes and may now start at any vertex and finish at any vertex. A route is required that excludes all those pipes directly attached to B .
\item State all possible combinations of starting and finishing points so that the length of Kim's route is minimised. State the length of Kim's route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2015 Q4 [16]}}