| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2020 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Find parameter values from route length |
| Difficulty | Challenging +1.8 This is a multi-step route inspection problem requiring the Chinese Postman algorithm, identification of odd vertices, shortest path calculations, and solving simultaneous equations from given constraints. It combines several algorithmic techniques and requires careful systematic work, making it significantly harder than standard Further Maths questions but not requiring exceptional insight. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| The graph has exactly two odd nodes and so the graph is semi-Eulerian | B1 | Explanation that the graph has two odd nodes, or stating graph is semi-Eulerian |
| dB1 | Exactly two odd nodes (or two odd nodes and five even nodes) together with deduction that graph is semi-Eulerian | |
| Total | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Dijkstra's algorithm applied correctly (larger number replaced by smaller in two working value boxes at C, D, G or F) | M1 | For a larger number replaced by a smaller one in two working value boxes |
| All values correct (and in correct order) at A, B and C | A1 | |
| All values correct (and in correct order) at E and D | A1 | |
| All values correct (and in correct order) at G and F | A1 | |
| Shortest path from A to F is \(58+x\) and shortest path from A to G is \(60+y\) | A1ft | Length of shortest paths stated (may be seen in equations) |
| \(58 + x + 60 + y = 140\) | M1 | (length of shortest path A to F) + (length of shortest path A to G) = 140; linear equation in \(x\) and \(y\) |
| The only odd nodes in the network are A and G | B1 | Could be implied by subsequent working |
| Route inspection: shortest route between A and G is \(60+y\), \(\Rightarrow 320 + x + y + 60 + y = 409\) | M1 | Equation based on route from A to G; \(320 + x + y +\) final value at G (in \(y\)) \(= 409\) |
| \(x = 15\) and \(y = 7\) | A1 | CAO |
| Total | (9) |
# Question 6:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| The graph has exactly two odd nodes and so the graph is semi-Eulerian | B1 | Explanation that the graph has two odd nodes, or stating graph is semi-Eulerian |
| | dB1 | Exactly two odd nodes (or two odd nodes and five even nodes) together with deduction that graph is semi-Eulerian |
| **Total** | **(2)** | |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Dijkstra's algorithm applied correctly (larger number replaced by smaller in two working value boxes at C, D, G or F) | M1 | For a larger number replaced by a smaller one in two working value boxes |
| All values correct (and in correct order) at A, B and C | A1 | |
| All values correct (and in correct order) at E and D | A1 | |
| All values correct (and in correct order) at G and F | A1 | |
| Shortest path from A to F is $58+x$ and shortest path from A to G is $60+y$ | A1ft | Length of shortest paths stated (may be seen in equations) |
| $58 + x + 60 + y = 140$ | M1 | (length of shortest path A to F) + (length of shortest path A to G) = 140; linear equation in $x$ and $y$ |
| The only odd nodes in the network are A and G | B1 | Could be implied by subsequent working |
| Route inspection: shortest route between A and G is $60+y$, $\Rightarrow 320 + x + y + 60 + y = 409$ | M1 | Equation based on route from A to G; $320 + x + y +$ final value at G (in $y$) $= 409$ |
| $x = 15$ and $y = 7$ | A1 | CAO |
| **Total** | **(9)** | |
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{bd357978-6464-43fd-854f-4188b5408e91-08_638_1107_212_479}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
[The total weight of the network is $320 + x + y$ ]
\begin{enumerate}[label=(\alph*)]
\item State, with justification, whether the graph in Figure 4 is Eulerian, semi-Eulerian or neither.
The weights on the arcs in Figure 4 represent distances. The weight on arc EF is $x$ where $12 < x < 26$ and the weight on arc DG is $y$ where $0 < y < 10$
An inspection route of minimum length that traverses each arc at least once is found.\\
The inspection route starts and finishes at A and has a length of 409\\
It is also given that the length of the shortest route from F to G via A is 140
\item Using appropriate algorithms, find the value of $x$ and the value of $y$.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2020 Q6 [11]}}