| Exam Board | AQA |
|---|---|
| Module | Further AS Paper 2 Discrete (Further AS Paper 2 Discrete) |
| Year | 2018 |
| Session | June |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST with cost calculation |
| Difficulty | Moderate -0.8 This is a straightforward application of Kruskal's or Prim's algorithm to find a minimum spanning tree with 6 vertices and 9 edges, followed by a simple multiplication to find cost. The algorithm is mechanical, the graph is small enough to solve by inspection, and no novel problem-solving is required—just standard recall and execution of a well-practiced procedure. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| From/To | Henhouse (H) | Goatshed (G) | Kennels (K) | Cattery (C) |
| Rainwater collection site (R) | 840 | 810 | 520 | 370 |
| Cattery (C) | - | 680 | 610 | \multirow{3}{*}{} |
| Duckpond (D) | 480 | 310 | ||
| Goatshed (G) | 150 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Sets up model and identifies one correct weight | M1 | |
| Identifies at least 4 correct weights (no more than 5) | M1 | Edges: \(RC=370\), \(CG=680\), \(GH=150\), \(KR=520\), \(DH=310\) |
| Minimum spanning tree identified: \(R\)-\(C\)-\(G\)-\(H\), \(K\)-\(R\), \(D\)-\(H\); total distance \(= 2030\) metres | A1 | Must state it is a minimum spanning tree; implied by use of Kruskal's or Prim's |
| Total weight of MST \(= 2030\) CAO | A1 | |
| \(2030 \times 0.60 = \pounds 1218\) | A1F | Uses total weight to find minimum cost with consistent unit |
## Question 6:
| Answer/Working | Mark | Guidance |
|---|---|---|
| Sets up model and identifies one correct weight | M1 | |
| Identifies at least 4 correct weights (no more than 5) | M1 | Edges: $RC=370$, $CG=680$, $GH=150$, $KR=520$, $DH=310$ |
| Minimum spanning tree identified: $R$-$C$-$G$-$H$, $K$-$R$, $D$-$H$; total distance $= 2030$ metres | A1 | Must state it is a minimum spanning tree; implied by use of Kruskal's or Prim's |
| Total weight of MST $= 2030$ CAO | A1 | |
| $2030 \times 0.60 = \pounds 1218$ | A1F | Uses total weight to find minimum cost with consistent unit |6 An animal sanctuary has a rainwater collection site.
The manager of the sanctuary is installing a pipe system to connect the rainwater collection site to five other sites in the sanctuary.
Each site does not need to be connected directly to the rainwater collection site.
There are nine possible routes between the sites that are suitable for water pipes.
The distances, in metres, of the nine possible routes are given in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
From/To & Henhouse (H) & Goatshed (G) & Kennels (K) & Cattery (C) \\
\hline
Rainwater collection site (R) & 840 & 810 & 520 & 370 \\
\hline
Cattery (C) & - & 680 & 610 & \multirow{3}{*}{} \\
\hline
Duckpond (D) & 480 & 310 & & \\
\hline
Goatshed (G) & 150 & & & \\
\hline
\end{tabular}
\end{center}
Water pipe costs 60 pence per metre.
Find the minimum cost of connecting all the sites to the rainwater collection site.
Fully justify your answer.\\
$7 \quad$ A linear programming problem has the constraints
$$\begin{aligned}
1 \leq x & \leq 6 \\
1 \leq y & \leq 6 \\
y & \geq x \\
x + y & \leq 11
\end{aligned}$$
\hfill \mbox{\textit{AQA Further AS Paper 2 Discrete 2018 Q6 [5]}}