| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST with variable edge weight |
| Difficulty | Moderate -0.3 This is a standard Decision Maths MST question with routine application of Kruskal's algorithm. Part (a) is straightforward algorithmic execution with x=8. Part (b) requires understanding when CD would be included, involving simple comparison of edge weights—accessible reasoning but slightly above pure recall due to the variable analysis component. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| (i) \(BD\) (5), \(AE\) (6), \(BE\) (7), \(BC\) (8) | M1 | SCA; first 3 edges of 4 edges in correct order, accept vertices in reverse order e.g. DB instead of BD |
| A1 | All correct; (must be edges not lengths) | |
| (ii) Spanning tree; all correct including labelling | B1 | |
| (iii) 26 | B1 | 4 marks total |
| Answer | Marks | Guidance |
|---|---|---|
| (i) e.g. \((BD, AE, BE,)\) BC would then be included, not CD or e.g. \(x\) is not less than 10 so \(x\) cannot equal 7 | E1 | oe; Do not accept answers which suggest a cycle |
| (ii) \(x \geq 10\) | B2 | 3 marks total |
**(a)** Accept answers for part (a) in any order or all together.
**(i)** $BD$ (5), $AE$ (6), $BE$ (7), $BC$ (8) | M1 | SCA; first 3 edges of 4 edges in correct order, accept vertices in reverse order e.g. DB instead of BD
| A1 | All correct; (must be edges not lengths)
**(ii)** Spanning tree; all correct including labelling | B1 |
**(iii)** 26 | B1 | 4 marks total
**(b)** Accept answers for part (b) in any order or all together
**(i)** e.g. $(BD, AE, BE,)$ BC would then be included, not CD or e.g. $x$ is not less than 10 so $x$ cannot equal 7 | E1 | oe; Do not accept answers which suggest a cycle
**(ii)** $x \geq 10$ | B2 | 3 marks total | SC1 $x > 10$ or $10 \leq x < n$ or $10 \leq x \leq n$ but $10 < x < n$ scores B0
**Total: 7 marks**
---3 The network below shows vertices $A , B , C , D$ and $E$. The number on each edge shows the distance between vertices.\\
\includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-06_563_736_402_651}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item In the case where $x = 8$, use Kruskal's algorithm to find a minimum spanning tree for the network. Write down the order in which you add edges to your minimum spanning tree.
\item Draw your minimum spanning tree.
\item Write down the length of your minimum spanning tree.
\end{enumerate}\item Alice draws the same network but changes the value of $x$. She correctly uses Kruskal's algorithm and edge $C D$ is included in her minimum spanning tree.
\begin{enumerate}[label=(\roman*)]
\item Explain why $x$ cannot be equal to 7 .
\item Write down an inequality for $x$.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2016 Q3 [7]}}