| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2015 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST with vertex removed |
| Difficulty | Moderate -0.8 This is a straightforward MST application question. Part (a) is routine Prim's algorithm execution with cost calculation (standard D1 content). Part (b) requires finding a new MST with one edge removed, which is a simple modification requiring minimal problem-solving—just re-apply the algorithm or remove CE and add the next cheapest edge that maintains connectivity. The question is easier than average A-level maths due to being algorithmic/procedural rather than requiring mathematical insight or proof. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| From \(A\): select \(AC=4\) (1st) | M1 | Prim's algorithm applied correctly from \(A\) |
| Select \(AD=5\) (2nd) | A1 | first two edges correct |
| Select \(CD=7\) rejected (cycle); select \(CE=6\) or \(BC=9\) etc.; correct sequence continuing | M1 | correct rejection of cycle-forming edge |
| Correct order: \(AC, AD, CE, EF, EH(4), GF\) or equivalent giving edges of weight \(4,5,6,8,4,7\) or similar | A1 | all 7 edges selected in correct Prim's order |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct minimum spanning tree drawn with 7 edges | B1 | correct tree topology |
| Total weight \(= 4+5+6+7+8+4+5 = 39\) (or correct sum for their tree) | B1 | correct weight stated |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Minimum cost \(= 39 \times 30 = \pounds1170\) | B1 | follow through from their MST total |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Remove \(CE\) from the MST; must find replacement edge not using \(CE\) | M1 | identifies need to replace \(CE=6\) with next best alternative |
| Replace with next cheapest edge connecting the two subtrees e.g. \(BC=9\); new total \(= 39 - 6 + 9 = 42\); cost \(= 42 \times 30 = \pounds1260\) | A1 | correct new cost |
# Question 2:
**(a)(i)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| From $A$: select $AC=4$ (1st) | M1 | Prim's algorithm applied correctly from $A$ |
| Select $AD=5$ (2nd) | A1 | first two edges correct |
| Select $CD=7$ rejected (cycle); select $CE=6$ or $BC=9$ etc.; correct sequence continuing | M1 | correct rejection of cycle-forming edge |
| Correct order: $AC, AD, CE, EF, EH(4), GF$ or equivalent giving edges of weight $4,5,6,8,4,7$ or similar | A1 | all 7 edges selected in correct Prim's order |
**(a)(ii)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct minimum spanning tree drawn with 7 edges | B1 | correct tree topology |
| Total weight $= 4+5+6+7+8+4+5 = 39$ (or correct sum for their tree) | B1 | correct weight stated |
**(a)(iii)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Minimum cost $= 39 \times 30 = \pounds1170$ | B1 | follow through from their MST total |
**(b)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Remove $CE$ from the MST; must find replacement edge not using $CE$ | M1 | identifies need to replace $CE=6$ with next best alternative |
| Replace with next cheapest edge connecting the two subtrees e.g. $BC=9$; new total $= 39 - 6 + 9 = 42$; cost $= 42 \times 30 = \pounds1260$ | A1 | correct new cost |
---2 The network below shows 8 towns, $A , B , \ldots , H$. The number on each edge shows the length of the road, in miles, between towns. During the winter, the council treats some of the roads with salt so that each town can be safely reached on treated roads from any other town. It costs $\pounds 30$ to treat a mile of road.\\
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-04_876_1611_497_210}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Prim's algorithm starting from $A$, showing the order in which you select the edges, to find a minimum spanning tree for the network.
\item Draw your minimum spanning tree.
\item Calculate the minimum cost to the council of making it possible for each town to be safely reached on treated roads from any other town.
\end{enumerate}\item On one occasion, the road from $C$ to $E$ is impassable because of flooding. Find the minimum cost of treating sufficient roads for safe travel in this case.\\[0pt]
[2 marks]
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2015 Q2 [9]}}