| Exam Board | Edexcel |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Year | 2020 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST with variable edge weight |
| Difficulty | Challenging +1.8 This question requires understanding MST algorithms (Prim's), analyzing uniqueness conditions through inequality constraints, and applying the Chinese Postman algorithm with a variable parameter. Part (b) demands systematic comparison of edge weights to establish when the given selection order is unique, requiring multiple inequalities. Part (c) combines route inspection with algebraic manipulation. While the individual techniques are A-level standard, the multi-step reasoning with a variable parameter and the need to synthesize several algorithmic concepts elevates this significantly above routine textbook exercises. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Each arc contributes 1 to the orders of two nodes, so the sum of the orders of all nodes equals twice the number of arcs | B1 | 1.2 - Award for: "Sum of orders = 2(number of arcs)" or "Each edge contributes 1 to order of two vertices" or "Sum of orders is even" |
| Therefore the sum of orders of all nodes is even, so there must be an even (or zero) number of vertices of odd order; hence there cannot be an odd number of vertices of odd order | B1dep | 2.4 - Dependent on B1; full correct conclusion required |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Either \(2x + 10 > 3x - 2\) or \(2x + 10 > 20\) | M1 | 3.1b - Comparing arc AB with AD or BD with AB |
| \(x < 12\) | A1 | 1.1b |
| \(x > 5\) | A1 | 1.1b |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Applies route inspection algorithm to this non-standard case (four odd nodes C, E, F, H) | M1 | 3.1b - Correct three pairings of the four odd nodes |
| \(C(GF)E + F(GD)H = 37 + 25 = 62\) | A1 | 1.1b - Any one correct pairing and total |
| \(C(G)F + E(FGD)H = 25 + 37 = 62\) | A1 | 1.1b - Any two correct pairings and totals |
| \(C(GD)H + EF = 30 + 12 = 42^*\) | A1 | 1.1b - All three correct pairings and totals |
| \(5x + 246 + 42 = 318\) | M1dep | 3.1a - Setting up equation using given values and smallest pairing |
| \(x = 6\) | A1 | 2.2a |
## Question 3:
**Part 3(a):**
| Answer | Mark | Guidance |
|--------|------|----------|
| Each arc contributes 1 to the orders of two nodes, so the sum of the orders of all nodes equals twice the number of arcs | B1 | 1.2 - Award for: "Sum of orders = 2(number of arcs)" or "Each edge contributes 1 to order of two vertices" or "Sum of orders is even" |
| Therefore the sum of orders of all nodes is even, so there must be an even (or zero) number of vertices of odd order; hence there cannot be an odd number of vertices of odd order | B1dep | 2.4 - Dependent on B1; full correct conclusion required |
**Part 3(b):**
| Answer | Mark | Guidance |
|--------|------|----------|
| Either $2x + 10 > 3x - 2$ or $2x + 10 > 20$ | M1 | 3.1b - Comparing arc AB with AD or BD with AB |
| $x < 12$ | A1 | 1.1b |
| $x > 5$ | A1 | 1.1b |
**Part 3(c):**
| Answer | Mark | Guidance |
|--------|------|----------|
| Applies route inspection algorithm to this non-standard case (four odd nodes C, E, F, H) | M1 | 3.1b - Correct three pairings of the four odd nodes |
| $C(GF)E + F(GD)H = 37 + 25 = 62$ | A1 | 1.1b - Any one correct pairing and total |
| $C(G)F + E(FGD)H = 25 + 37 = 62$ | A1 | 1.1b - Any two correct pairings and totals |
| $C(GD)H + EF = 30 + 12 = 42^*$ | A1 | 1.1b - All three correct pairings and totals |
| $5x + 246 + 42 = 318$ | M1dep | 3.1a - Setting up equation using given values and smallest pairing |
| $x = 6$ | A1 | 2.2a |3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{a2a6e659-aab5-4eec-9af4-ca6ab895f1c8-04_720_1470_233_296}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
[The weight of the network is $5 x + 246$ ]
\begin{enumerate}[label=(\alph*)]
\item Explain why it is not possible to draw a graph with an odd number of vertices of odd valency.
Figure 2 represents a network of 14 roads in a town. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
Prim's algorithm, starting at A, is applied to the network. The order in which the arcs are selected is $\mathrm { AD } , \mathrm { DH } , \mathrm { DG } , \mathrm { FG } , \mathrm { EF } , \mathrm { CG } , \mathrm { BD }$. It is given that the order in which the arcs are selected is unique.
\item Using this information, find the smallest possible range of values for $x$, showing your working clearly.
A route that minimises the total time taken to traverse each road at least once is required. The route must start and finish at the same vertex.
Given that the time taken to traverse this route is 318 minutes,
\item use an appropriate algorithm to determine the value of $x$, showing your working clearly.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 AS 2020 Q3 [11]}}