| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2024 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Chinese Postman with different start/end |
| Difficulty | Standard +0.8 This is a multi-part Chinese Postman problem requiring Dijkstra's algorithm, systematic consideration of multiple vertex pairings for odd-degree vertices, and comparison of routes under different network conditions. While the techniques are standard for Further Maths Decision modules, the question requires careful bookkeeping across three parts with changing constraints, making it moderately challenging but still within typical FD1 scope. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| A larger value replaced by smaller value in at least two working boxes at B, D, F, H, K or J | M1 | |
| All values in A, B, C, D and E correct | A1 | Condone lack of 0 in A's working value |
| All values G, F and H correct with working values in correct order | A1 | G, F, H must be labelled in that order, after A,B,C,D,E |
| All values in K and J correct on follow through, working values in correct order | A1ft | |
| Correct path from A to J: ACBDGFHJ | A1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| If finishing at J, pair A,B,C,K: \(AB+CK=23+73=96\); \(AC+BK=18+68=86^*\); \(AK+BC=91+5=96\) | M1 | One correct set of three distinct pairings |
| Any three rows correct including pairings and totals | A1ft | |
| If finishing at K, pair A,B,C,J: \(AB+CJ=23+76=99\); \(AC+BJ=18+71=89\); \(AJ+BC=94+5=99\) | dM1 | All six distinct pairings; dependent on first M1 |
| All six rows correct including pairings and totals | A1ft | |
| Finish at J; repeated edges AC, BD, DG, GF, FH, HK | A1 | CAO; must clearly select finishing at J |
| Total length \(413 + 86 = 499\) (km) | A1ft | \(413 +\) their "86" |
| Answer | Marks |
|---|---|
| Tarig's route length: \((94+2)-5-6=85\) or with addition of 413: \(413+94+2-5-6=498\) | M1 |
| Therefore Tarig's route is shorter (498 vs 499 or 85 vs 86 seen) | A1 |
# Question 3:
## Part (a)
| A larger value replaced by smaller value in at least two working boxes at B, D, F, H, K or J | M1 | |
| All values in A, B, C, D and E correct | A1 | Condone lack of 0 in A's working value |
| All values G, F and H correct with working values in correct order | A1 | G, F, H must be labelled in that order, after A,B,C,D,E |
| All values in K and J correct on follow through, working values in correct order | A1ft | |
| Correct path from A to J: ACBDGFHJ | A1 | CAO |
**(5)**
## Part (b)
| If finishing at J, pair A,B,C,K: $AB+CK=23+73=96$; $AC+BK=18+68=86^*$; $AK+BC=91+5=96$ | M1 | One correct set of three distinct pairings |
| Any three rows correct including pairings and totals | A1ft | |
| If finishing at K, pair A,B,C,J: $AB+CJ=23+76=99$; $AC+BJ=18+71=89$; $AJ+BC=94+5=99$ | dM1 | All six distinct pairings; dependent on first M1 |
| All six rows correct including pairings and totals | A1ft | |
| Finish at J; repeated edges AC, BD, DG, GF, FH, HK | A1 | CAO; must clearly select finishing at J |
| Total length $413 + 86 = 499$ (km) | A1ft | $413 +$ their "86" |
**(6)**
## Part (c)
| Tarig's route length: $(94+2)-5-6=85$ or with addition of 413: $413+94+2-5-6=498$ | M1 | |
| Therefore Tarig's route is shorter (498 vs 499 or 85 vs 86 seen) | A1 | |
**(2)**3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{7f7546eb-0c1a-40da-bdf0-31e0574a9867-06_764_1136_258_466}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
[The total weight of the network is 413]
Figure 1 represents a network of cycle tracks between ten towns, A, B, C, D, E, F, G, H, J and K. The number on each arc represents the length, in kilometres, of the corresponding track.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest path from A to J.
Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K.
Abi wishes to minimise the total distance required to traverse every track.
\item By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must
\begin{itemize}
\item state which tracks she will repeat in her route
\item state the total length of her route
\end{itemize}
The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H.
Tarig wishes to minimise the total length of his inspection route.
\item Determine which route, Abi's or Tarig's, is shorter. You must make your working clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2024 Q3 [13]}}