| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Year | 2021 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Maximize spanning tree weight |
| Difficulty | Standard +0.3 This is a straightforward maximum spanning tree problem requiring application of a standard algorithm (reverse Kruskal's or modified Prim's) with minimal adaptation. While it's Further Maths content, the execution is mechanical: select edges in descending weight order avoiding cycles. Parts (b) and (c) add minor extensions but require only basic reasoning about the model's assumptions and recalculation after removing one edge. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Using Prim's algorithm, listing at least 4 correct labelled arcs: \(X\)–\(B\): 3.0, \(B\)–\(C\): 3.5, \(B\)–\(E\): 3.0, \(E\)–\(G\): 4.5, \(G\)–\(H\): 5.5, \(D\)–\(E\): 4.0, \(A\)–\(D\): 3.0, \(C\)–\(F\): 2.5 | M1 | AO 3.3; sets up model finding maximum spanning tree |
| Correct 8 arcs of the maximum spanning tree | A1 | AO 3.4 |
| Answer | Marks | Guidance |
|---|---|---|
| \(3.0 + 3.5 + 3.0 + 4.5 + 5.5 + 4.0 + 3.0 + 2.5\) | M1 | AO 3.1b; finds total of weights of 8 arcs |
| \(= 29\) tonnes | A1F | AO 3.2a; correct estimate with units from their model |
| Answer | Marks | Guidance |
|---|---|---|
| The values used to arrive at 29 tonnes are estimates, so 29 tonnes is an estimate for the maximum amount of precious metal | E1 | AO 2.4; explains values used in calculating (a)(ii) are estimates |
| The true value may be more than or less than 29 tonnes | E1 | AO 2.2b; infers true maximum may be more or less than estimate |
| Answer | Marks | Guidance |
|---|---|---|
| \(CF\) is part of the spanning tree that maximises the estimate; either \(EF\) or \(HF\) will need excavating instead as they both have weight 3.0 | M1 | AO 3.5a; evaluates removal of \(CF\) from model |
| Estimate reduces by 0.5 tonnes to 28.5 tonnes (condone omission of units) | A1 | AO 1.1b |
## Question 3(a)(i):
Using Prim's algorithm, listing at least 4 correct labelled arcs: $X$–$B$: 3.0, $B$–$C$: 3.5, $B$–$E$: 3.0, $E$–$G$: 4.5, $G$–$H$: 5.5, $D$–$E$: 4.0, $A$–$D$: 3.0, $C$–$F$: 2.5 | M1 | AO 3.3; sets up model finding maximum spanning tree
Correct 8 arcs of the maximum spanning tree | A1 | AO 3.4
---
## Question 3(a)(ii):
$3.0 + 3.5 + 3.0 + 4.5 + 5.5 + 4.0 + 3.0 + 2.5$ | M1 | AO 3.1b; finds total of weights of 8 arcs
$= 29$ tonnes | A1F | AO 3.2a; correct estimate with units from their model
---
## Question 3(b):
The values used to arrive at 29 tonnes are estimates, so 29 tonnes is an estimate for the maximum amount of precious metal | E1 | AO 2.4; explains values used in calculating (a)(ii) are estimates
The true value may be more than or less than 29 tonnes | E1 | AO 2.2b; infers true maximum may be more or less than estimate
---
## Question 3(c):
$CF$ is part of the spanning tree that maximises the estimate; either $EF$ or $HF$ will need excavating instead as they both have weight 3.0 | M1 | AO 3.5a; evaluates removal of $CF$ from model
Estimate reduces by 0.5 tonnes to 28.5 tonnes (condone omission of units) | A1 | AO 1.1b
---3 A mining company wants to open a new mine in an area where the ground contains a precious metal.
The mining company has carried out a survey of the area. The network below shows nodes which represent the entrance to the new mine, $X$, and the 8 ventilation shafts, $A , B , \ldots , H$, which have been installed to prevent the build up of dangerous gases underground.\\
\includegraphics[max width=\textwidth, alt={}, center]{59347089-ea4a-4ee6-b40e-1ab78aa7cdc3-04_846_1228_623_404}
Each arc represents a possible underground tunnel which could be mined.\\
The weight on each arc represents the estimated amount of precious metal in that possible underground tunnel in tonnes.
Due to geological reasons, the mining company can only create 8 underground tunnels.
All 8 ventilation shafts must be accessible from the entrance of the mine.
3
\begin{enumerate}[label=(\alph*)]
\item (i) The mining company wants to maximise the amount of precious metal it can extract from the new mine.
Determine the tunnels the mining company should use.\\
3 (a) (ii) Estimate the maximum amount of precious metal the mining company can extract from the new mine.
3
\item Comment on why the maximum amount of precious metal the mining company can extract from the new mine may be different from your answer to part (a)(ii).\\[0pt]
[2 marks]\\
3
\item Before the mining company begins work on the new mine, a government survey prevents the mining company drilling the tunnel represented by $C F$.
Determine the effect, if any, the government survey has on your answers to part (a)(i) and part (a)(ii).
\end{enumerate}
\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2021 Q3 [8]}}