| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Easy -1.2 This is a standard textbook application of Prim's algorithm with straightforward follow-up questions. The algorithm is mechanical and requires no problem-solving insight—students simply follow the procedure they've learned. Parts (b) and (c) test basic understanding of how different starting points and algorithms affect edge selection order, but the MST itself remains unchanged. This is routine recall and application, easier than average A-level maths questions. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(AB = 6.1\) selected 1st | B1 | Must start from \(A\) |
| \(BE = 9.7\) selected 2nd | M1 | Correct application of Prim's from \(A\) |
| \(DE = 7.2\) selected 3rd | A1 | |
| \(HI = 6.7\) selected 4th | A1 | |
| \(EH = 12.5\) selected 5th (or \(GH = 8.9\)) | A1 | |
| \(GH = 8.9\) selected 6th (or \(EH\)) | A1 | |
| \(BC = 7.4\) selected 7th | A1 | Accept correct order throughout; all 8 edges correct |
| \(CF = 11.3\) selected 8th |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(6.1 + 9.7 + 7.2 + 6.7 + 12.5 + 8.9 + 7.4 + 11.3 = 69.8\) miles | B1 | Follow through from their spanning tree (must have 8 edges connecting 9 nodes) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Correct tree drawn with edges: \(AB, BE, DE, HI, EH, GH, BC, CF\) | B1 | Follow through from (a)(i); must be a tree (no cycles) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| (i) Start vertex \(E\): final edge is \(CF = 11.3\) | B1 | |
| (ii) Start vertex \(G\): final edge is \(CF = 11.3\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| (i) First edge included: \(HI = 6.7\) | B1 | Smallest weight edge |
| (ii) Last edge included: \(CF = 11.3\) | B1 | Largest edge in the MST |
# Question 4:
## Part (a)(i) - Prim's Algorithm from A
| Answer | Mark | Guidance |
|--------|------|----------|
| $AB = 6.1$ selected 1st | B1 | Must start from $A$ |
| $BE = 9.7$ selected 2nd | M1 | Correct application of Prim's from $A$ |
| $DE = 7.2$ selected 3rd | A1 | |
| $HI = 6.7$ selected 4th | A1 | |
| $EH = 12.5$ selected 5th (or $GH = 8.9$) | A1 | |
| $GH = 8.9$ selected 6th (or $EH$) | A1 | |
| $BC = 7.4$ selected 7th | A1 | Accept correct order throughout; all 8 edges correct |
| $CF = 11.3$ selected 8th | | |
## Part (a)(ii) - Length of MST
| Answer | Mark | Guidance |
|--------|------|----------|
| $6.1 + 9.7 + 7.2 + 6.7 + 12.5 + 8.9 + 7.4 + 11.3 = 69.8$ miles | B1 | Follow through from their spanning tree (must have 8 edges connecting 9 nodes) |
## Part (a)(iii) - Draw MST
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct tree drawn with edges: $AB, BE, DE, HI, EH, GH, BC, CF$ | B1 | Follow through from (a)(i); must be a tree (no cycles) |
## Part (b) - Final edge with different start vertices
| Answer | Mark | Guidance |
|--------|------|----------|
| (i) Start vertex $E$: final edge is $CF = 11.3$ | B1 | |
| (ii) Start vertex $G$: final edge is $CF = 11.3$ | B1 | |
## Part (c) - Kruskal's Algorithm
| Answer | Mark | Guidance |
|--------|------|----------|
| (i) First edge included: $HI = 6.7$ | B1 | Smallest weight edge |
| (ii) Last edge included: $CF = 11.3$ | B1 | Largest edge in the MST |4 The following network shows the lengths, in miles, of roads connecting nine villages, $A , B , \ldots , I$.
A programme of resurfacing some roads is undertaken to ensure that each village can access all other villages along a resurfaced road, while keeping the amount of road to be resurfaced to a minimum.\\
\includegraphics[max width=\textwidth, alt={}, center]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-08_1008_1043_589_497}
\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 State the length of your minimum spanning tree.
\item Draw your minimum spanning tree.
\end{enumerate}\item Given that Prim's algorithm is used with different start vertices, state the final edge to be added to the minimum spanning tree if:
\begin{enumerate}[label=(\roman*)]
\item the start vertex is $E$;
\item the start vertex is $G$.
\end{enumerate}\item Given that Kruskal's algorithm is used to find the minimum spanning tree, state which edge would be:
\begin{enumerate}[label=(\roman*)]
\item the first to be included in the tree;
\item the last to be included in the tree.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2013 Q4 [11]}}