| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2018 |
| Session | Specimen |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Define tree terminology |
| Difficulty | Easy -1.3 This is a standard D1 textbook question testing basic definitions (connected graph, tree, spanning tree), recall of a simple formula (n-1 arcs), and routine application of Kruskal's algorithm to a small network. It requires no problem-solving insight—just following a memorized procedure step-by-step. Significantly easier than average A-level maths questions. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | G | |
| A | -- | 17 | -- | 19 | 30 | -- | -- |
| B | 17 | -- | 21 | 23 | -- | -- | -- |
| C | -- | 21 | -- | 27 | 29 | 31 | 22 |
| D | 19 | 23 | 27 | -- | -- | 40 | -- |
| E | 30 | -- | 29 | -- | -- | 33 | 25 |
| F | -- | -- | 31 | 40 | 33 | -- | 39 |
| G | -- | -- | 22 | -- | 25 | 39 | -- |
| Answer | Marks | Guidance |
|---|---|---|
| e.g. accept (i) Every pair of nodes connected by a path; (ii) Connected graph with no cycles; (iii) All nodes connected | B1 × 3 | Technical language must be correct – do not accept 'point' for node, etc. |
| Answer | Marks | Guidance |
|---|---|---|
| \(n - 1\) | B1 | cao (ignore lack of units) |
| Answer | Marks |
|---|---|
| [Graph with weighted edges shown] | M1, A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Kruskal: AB, AD, BC, CG, reject BD, EG, reject CD, reject CE, reject AE, CF | M1 A1, A1 | Kruskal's – first three arcs (AB, AD, BC, … or weights 17, 19, 21, …) chosen correctly and at least one rejection seen at some point. For M1 only: follow through from their diagram in (c). All six arcs (AB, AD, BC, CG, EG, CF or weights 17, 19, 21, 22, 25, 31) chosen correctly and no additional arcs (no follow through from an incorrect network in (c)) |
| Answer | Marks | Guidance |
|---|---|---|
| \(135\) (km) | B1 | cao (ignore lack of units) |
## 2(a)
e.g. accept (i) Every pair of nodes connected by a path; (ii) Connected graph with no cycles; (iii) All nodes connected | B1 × 3 | Technical language must be correct – do not accept 'point' for node, etc.
## 2(b)
$n - 1$ | B1 | cao (ignore lack of units)
## 2(c)
[Graph with weighted edges shown] | M1, A1 |
## 2(d)
Kruskal: AB, AD, BC, CG, reject BD, EG, reject CD, reject CE, reject AE, CF | M1 A1, A1 | Kruskal's – first three arcs (AB, AD, BC, … or weights 17, 19, 21, …) chosen correctly and at least one rejection seen at some point. For M1 only: follow through from their diagram in (c). All six arcs (AB, AD, BC, CG, EG, CF or weights 17, 19, 21, 22, 25, 31) chosen correctly and no additional arcs (no follow through from an incorrect network in (c))
## 2(e)
$135$ (km) | B1 | cao (ignore lack of units)
---Kruskal's algorithm finds a minimum spanning tree for a connected graph with $n$ vertices.
\begin{enumerate}[label=(\alph*)]
\item Explain the terms
\begin{enumerate}[label=(\roman*)]
\item connected graph,
\item tree,
\item spanning tree.
\end{enumerate}
\hfill [3]
\item Write down, in terms of $n$, the number of arcs in the minimum spanning tree. \hfill [1]
\end{enumerate}
The table below shows the lengths, in km, of a network of roads between seven villages, A, B, C, D, E, F and G.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
& A & B & C & D & E & F & G \\
\hline
A & -- & 17 & -- & 19 & 30 & -- & -- \\
\hline
B & 17 & -- & 21 & 23 & -- & -- & -- \\
\hline
C & -- & 21 & -- & 27 & 29 & 31 & 22 \\
\hline
D & 19 & 23 & 27 & -- & -- & 40 & -- \\
\hline
E & 30 & -- & 29 & -- & -- & 33 & 25 \\
\hline
F & -- & -- & 31 & 40 & 33 & -- & 39 \\
\hline
G & -- & -- & 22 & -- & 25 & 39 & -- \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{2}
\item Complete the drawing of the network on Diagram 1 in the answer book by adding the necessary arcs from vertex C together with their weights. \hfill [2]
\item Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. \hfill [3]
\item State the weight of the minimum spanning tree. \hfill [1]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2018 Q2 [10]}}