| Exam Board | Edexcel |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Year | 2022 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | State Eulerian/semi-Eulerian classification |
| Difficulty | Moderate -0.5 Part (b) requires only checking vertex degrees and applying the definition of Eulerian/semi-Eulerian—a direct recall task. While the question involves multiple parts including Dijkstra's algorithm and route inspection, part (b) specifically is a straightforward classification requiring minimal problem-solving, making it easier than average for A-level Further Maths. |
| Spec | 7.02c Graph terminology: walk, trail, path, cycle, route7.02g Eulerian graphs: vertex degrees and traversability7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A path is a (i) finite sequence of edges, such that (ii) the end vertex of one edge is the start vertex of the next, and (iii) no vertex appears more than once | B2,1,0 | One mark for one point clearly made; condone 'a vertex cannot appear twice' but not 'a vertex cannot be repeated more than once' |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Graph is neither Eulerian nor semi-Eulerian because it has six odd vertices | B1 | Must state 'neither'; argument must be convincing; do not award if any incorrect reasoning given |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct Dijkstra's algorithm applied — larger value replaced by smaller at least twice in working values at C, F, G, H | M1 | Order of labelling must be strictly increasing sequence |
| All values at A, B, D, C correct with working values in correct order | A1 (ABDC) | |
| All values at F and E correct with working values in correct order | A1 (FE) | Condone additional working value of 18 after 17 at E |
| All values at G and H correct on follow-through, working values in correct order | A1ft (GH) | Condone additional working value of 32 after 22 at H |
| Shortest path: ABEH | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| If arc CD included: \(AE + GH = 17 + 12 = 29\), \(AG + EH = 20 + 5 = 25\), \(AH + EG = 22 + 10 = 32\) | M1 | One correct set (AEGH or ACDH) of three distinct pairings of the correct four odd nodes |
| Any three rows correct including pairings and totals from either set | A1 | |
| If arc EG included: \(AC + DH = 11 + 17 = 28\), \(AD + CH = 10 + 12 = 22^*\), \(AH + CD = 22 + 11 = 33\) | depM1 | All six distinct pairings for nodes AEGH and ACDH |
| All six rows correct including pairings and totals | A1 | |
| Track EG with repeated arcs AD, CF, FE, EH | A1 | Must be clearly stated, not just in working |
| Length \(= 120 + 9 + 22 = 151\) km | A1 | cao — dependent on first four marks in this part |
# Question 3:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| A path is a (i) finite sequence of edges, such that (ii) the end vertex of one edge is the start vertex of the next, and (iii) no vertex appears more than once | B2,1,0 | One mark for one point clearly made; condone 'a vertex cannot appear twice' but not 'a vertex cannot be repeated more than once' |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Graph is neither Eulerian nor semi-Eulerian because it has six odd vertices | B1 | Must state 'neither'; argument must be convincing; do not award if any incorrect reasoning given |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct Dijkstra's algorithm applied — larger value replaced by smaller at least twice in working values at C, F, G, H | M1 | Order of labelling must be strictly increasing sequence |
| All values at A, B, D, C correct with working values in correct order | A1 (ABDC) | |
| All values at F and E correct with working values in correct order | A1 (FE) | Condone additional working value of 18 after 17 at E |
| All values at G and H correct on follow-through, working values in correct order | A1ft (GH) | Condone additional working value of 32 after 22 at H |
| Shortest path: ABEH | A1 | cao |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| If arc CD included: $AE + GH = 17 + 12 = 29$, $AG + EH = 20 + 5 = 25$, $AH + EG = 22 + 10 = 32$ | M1 | One correct set (AEGH or ACDH) of three distinct pairings of the correct four odd nodes |
| Any three rows correct including pairings and totals from either set | A1 | |
| If arc EG included: $AC + DH = 11 + 17 = 28$, $AD + CH = 10 + 12 = 22^*$, $AH + CD = 22 + 11 = 33$ | depM1 | All six distinct pairings for nodes AEGH and ACDH |
| All six rows correct including pairings and totals | A1 | |
| Track EG with repeated arcs AD, CF, FE, EH | A1 | Must be clearly stated, not just in working |
| Length $= 120 + 9 + 22 = 151$ km | A1 | cao — dependent on first four marks in this part |
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{c8134d3b-71cb-4b92-ac54-81a4ff8f3011-05_702_1479_201_293}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
[The total weight of the network is 120]
\begin{enumerate}[label=(\alph*)]
\item Explain what is meant by the term "path".
\item State, with a reason, whether the network in Figure 2 is Eulerian, semi-Eulerian or neither.
Figure 2 represents a network of cycle tracks between eight villages, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }$ and H . The number on each arc represents the length, in km , of the corresponding track. Samira lives in village A, and wishes to visit her friend, Daisy, who lives in village H.
\item Use Dijkstra's algorithm to find the shortest path that Samira can take.
An extra cycle track of length 9 km is to be added to the network. It will either go directly between C and D or directly between E and G .
Daisy plans to cycle along every track in the new network, starting and finishing at H .\\
Given that the addition of either track CD or track EG will not affect the final values obtained in (c),
\item use a suitable algorithm to find out which of the two possible extra tracks will give Daisy the shortest route, making your method and working clear. You must
\begin{itemize}
\item state which tracks Daisy will repeat in her route
\item state the total length of her route
\end{itemize}
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 AS 2022 Q3 [14]}}