| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Session | Specimen |
| Marks | 3 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Calculate MST length/weight/cost |
| Difficulty | Moderate -0.8 This is a straightforward application of Kruskal's or Prim's algorithm to find an MST with only 5 vertices. The table is clearly presented, the algorithm is mechanical, and no problem-solving insight is required—just systematic application of a standard procedure taught in Decision Maths. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Alvanley | Dunham | Elton | Helsby | Ince | |
| Alvanley | - | 2000 | 4000 | 750 | 5500 |
| Dunham | 2000 | - | 2500 | 2250 | 4000 |
| Elton | 4000 | 2500 | - | 3000 | 1250 |
| Helsby | 750 | 2250 | 3000 | - | 4250 |
| Ince | 5500 | 4000 | 1250 | 4250 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Translates problem into finding a minimum spanning tree by listing or drawing 4 labelled arcs | M1 | Condone A for Alvanley etc |
| Alvanley to Helsby: 750, Elton to Ince: 1250, Alvanley to Dunham: 2000, Dunham to Elton: 2500 | A1 | Finds correctly 4 arcs of the minimum spanning tree by listing or drawing |
| \(750 + 1250 + 2000 + 2500 = 6500\) m | B1 | Determines correctly the total minimum length of cable required, complete with unit |
## Question 4:
| Answer | Mark | Guidance |
|--------|------|----------|
| Translates problem into finding a minimum spanning tree by listing or drawing 4 labelled arcs | M1 | Condone A for Alvanley etc |
| Alvanley to Helsby: 750, Elton to Ince: 1250, Alvanley to Dunham: 2000, Dunham to Elton: 2500 | A1 | Finds correctly 4 arcs of the minimum spanning tree by listing or drawing |
| $750 + 1250 + 2000 + 2500 = 6500$ m | B1 | Determines correctly the total minimum length of cable required, complete with unit |
---4 Optical fibre broadband cables are being installed between 5 neighbouring villages.
The distance between each pair of villages in metres is shown in the table.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Alvanley & Dunham & Elton & Helsby & Ince \\
\hline
Alvanley & - & 2000 & 4000 & 750 & 5500 \\
\hline
Dunham & 2000 & - & 2500 & 2250 & 4000 \\
\hline
Elton & 4000 & 2500 & - & 3000 & 1250 \\
\hline
Helsby & 750 & 2250 & 3000 & - & 4250 \\
\hline
Ince & 5500 & 4000 & 1250 & 4250 & - \\
\hline
\end{tabular}
\end{center}
The company installing the optical fibre broadband cables wishes to create a network connecting each of the 5 villages using the minimum possible length of cable.
Find the minimum length of cable required.\\[0pt]
[3 marks]
\hfill \mbox{\textit{AQA Further Paper 3 Discrete Q4 [3]}}