| Exam Board | AQA |
|---|---|
| Module | Further AS Paper 2 Discrete (Further AS Paper 2 Discrete) |
| Year | 2020 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | State number of edges formula |
| Difficulty | Easy -1.2 This is a straightforward application of basic MST theory. Part (a) requires recalling that a spanning tree on n vertices has n-1 edges (7 vertices → 6 edges). Part (b) is a standard Kruskal's/Prim's algorithm application with clear tabular data. Part (c) asks for conceptual understanding of how adding a zero-weight edge affects the MST, but requires no actual calculation. All parts are routine recall and standard procedures with no novel problem-solving required. |
| Spec | 7.02k Digraphs: directed graphs, indegree and outdegree7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Statue | \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | C | \(\boldsymbol { D }\) | \(E\) | \(F\) | \(G\) |
| \(\boldsymbol { A }\) | - | 4 | 7 | - | - | - | - |
| B | 4 | - | 6 | 2 | 3 | - | - |
| C | 7 | 6 | - | - | 3 | - | 4 |
| \(D\) | - | 2 | - | - | 4 | 5 | - |
| \(E\) | - | 3 | 3 | 4 | - | 3 | 7 |
| \(F\) | - | - | - | 5 | 3 | - | 6 |
| G | - | - | 4 | - | 7 | 6 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| If one statue connected to all others, there would be at least 6 paths connected to it; therefore minimum of 6 paths need to be wider | B1 | Uses model to explore minimum number of wider paths needed |
| All statues still need to be connected when using minimum number of wider paths; minimum is 6 | E1 | Explains reasoning that minimum is 6 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Using Prim's algorithm starting at \(A\): \(AB: 4\), \(BD: 2\), \(BE: 3\), \(EC: 3\), \(EF: 3\), \(CG: 4\) | M1 | Uses Prim's algorithm in the table |
| Correct arcs for minimum spanning tree as above | A1 | Finds the correct arcs |
| Sum of weights \(= 4+2+3+3+3+4 = 19\); therefore 19 trees need to be removed | A1 | Finds correct total weight and fully justifies answer by use of minimum spanning tree algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| In the minimum spanning tree, consider weights of arcs connected to \(A\), \(D\) and \(F\) | M1 | Uses the model to consider weights of arcs connected to \(A\), \(D\) and \(F\) |
| Arc \(AB\) has the largest weight of all arcs connected to \(A\), \(D\) and \(F\); therefore \(AB\) should not be used. Either \(AD\) or \(AF\) constructed instead | A1 | Explains that arc \(AB\) should not be used |
## Question 6(a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| If one statue connected to all others, there would be at least 6 paths connected to it; therefore minimum of 6 paths need to be wider | B1 | Uses model to explore minimum number of wider paths needed |
| All statues still need to be connected when using minimum number of wider paths; minimum is 6 | E1 | Explains reasoning that minimum is 6 |
## Question 6(b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Using Prim's algorithm starting at $A$: $AB: 4$, $BD: 2$, $BE: 3$, $EC: 3$, $EF: 3$, $CG: 4$ | M1 | Uses Prim's algorithm in the table |
| Correct arcs for minimum spanning tree as above | A1 | Finds the correct arcs |
| Sum of weights $= 4+2+3+3+3+4 = 19$; therefore 19 trees need to be removed | A1 | Finds correct total weight and fully justifies answer by use of minimum spanning tree algorithm |
## Question 6(c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| In the minimum spanning tree, consider weights of arcs connected to $A$, $D$ and $F$ | M1 | Uses the model to consider weights of arcs connected to $A$, $D$ and $F$ |
| Arc $AB$ has the largest weight of all arcs connected to $A$, $D$ and $F$; therefore $AB$ should not be used. Either $AD$ or $AF$ constructed instead | A1 | Explains that arc $AB$ should not be used |
---6 A garden has seven statues $A , B , C , D , E , F$ and $G$, with paths connecting each pair of statues, either directly or indirectly.
To provide better access to all the statues, some of the paths are being made wider.\\
6
\begin{enumerate}[label=(\alph*)]
\item State why six is the minimum number of paths that need to be made wider.
6
\item The table below shows the number of trees that need to be removed to make the path between adjacent statues wider.
A dash in the table means that there is no direct path between the two statues.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
Statue & $\boldsymbol { A }$ & $\boldsymbol { B }$ & C & $\boldsymbol { D }$ & $E$ & $F$ & $G$ \\
\hline
$\boldsymbol { A }$ & - & 4 & 7 & - & - & - & - \\
\hline
B & 4 & - & 6 & 2 & 3 & - & - \\
\hline
C & 7 & 6 & - & - & 3 & - & 4 \\
\hline
$D$ & - & 2 & - & - & 4 & 5 & - \\
\hline
$E$ & - & 3 & 3 & 4 & - & 3 & 7 \\
\hline
$F$ & - & - & - & 5 & 3 & - & 6 \\
\hline
G & - & - & 4 & - & 7 & 6 & - \\
\hline
\end{tabular}
\end{center}
Find the minimum number of trees that need to be removed.
Fully justify your answer.\\
6
\item A landscaper identifies that two new wide paths could be constructed without removing any trees. However, there are only enough resources to build one new wide path.
The new wide path could be between $A$ and $D$ or between $A$ and $F$.\\
Explain clearly how the solution to part (b) can be adapted to find the new minimum number of trees that need to be removed.\\[0pt]
[2 marks]
\end{enumerate}
\hfill \mbox{\textit{AQA Further AS Paper 2 Discrete 2020 Q6 [7]}}