| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Year | 2020 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST with cost calculation |
| Difficulty | Moderate -0.5 This is a standard MST application using Prim's or Kruskal's algorithm with straightforward cost calculation. The table is clearly presented, the algorithm is routine, and parts (ii) and (b) require only brief written explanations about practical constraints—typical for Decision Maths but easier than average A-level questions overall due to algorithmic nature. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Education | Housing | Refuse Collection | Payroll | Social Care | Transport | |
| Education | - | 27 | 13 | 35 | 16 | 24 |
| Housing | 27 | - | 29 | 30 | 22 | 24 |
| Refuse Collection | 13 | 29 | - | 26 | 23 | 17 |
| Payroll | 35 | 30 | 26 | - | 20 | 40 |
| Social Care | 16 | 22 | 23 | 20 | - | 21 |
| Transport | 24 | 24 | 17 | 40 | 21 | - |
3 A company is installing an internal telephone network between the offices in a council building. Each office is required to be connected with telephone cables, either directly or indirectly, to every other office in the building.
The lengths of cable, in metres, needed to connect the offices are shown in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& Education & Housing & Refuse Collection & Payroll & Social Care & Transport \\
\hline
Education & - & 27 & 13 & 35 & 16 & 24 \\
\hline
Housing & 27 & - & 29 & 30 & 22 & 24 \\
\hline
Refuse Collection & 13 & 29 & - & 26 & 23 & 17 \\
\hline
Payroll & 35 & 30 & 26 & - & 20 & 40 \\
\hline
Social Care & 16 & 22 & 23 & 20 & - & 21 \\
\hline
Transport & 24 & 24 & 17 & 40 & 21 & - \\
\hline
\end{tabular}
\end{center}
The council wants the total length of cable that is used to be as small as possible.\\
The cost to the council to install one metre of cable is $\pounds 8$\\
3
\begin{enumerate}[label=(\alph*)]
\item (i) Find the minimum total cost to the council to install the cable required for the internal telephone network.\\[0pt]
[4 marks]\\
3 (a) (ii) Suggest a reason why the total cost to the council for installing the internal telephone network is likely to be different from your answer to part (a)(i).
3
\item Before the company starts installing the cable, it is told that the Education office cannot be connected directly to the Transport office due to issues with the building.
Explain the possible impact of this on your answer to part (a)(i).
\end{enumerate}
\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2020 Q3 [8]}}