| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Identify specific edge in algorithm |
| Difficulty | Moderate -0.5 This is a standard textbook application of Kruskal's and Prim's algorithms with straightforward execution. Part (a) requires systematic edge selection by weight order, and part (b) asks students to identify final edges when using Prim's from different vertices—routine algorithmic work requiring careful bookkeeping but no problem-solving insight or novel reasoning. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Edges selected in order: \(B\)–\(C\) (2.5), \(H\)–\(J\) (2.9), \(E\)–\(F\) or \(D\)–\(E\) (wait — \(E\)–\(G\): 2.3), then \(A\)–\(B\) or next smallest… Correct order: 2.3 (\(E\)–\(G\)), 2.5 (\(A\)–\(B\)), 2.9 (\(H\)–\(J\)), 3.1 (\(A\)–\(C\)), 3.2 (\(A\)–\(D\) or \(C\)–\(D\)), 3.4 (\(G\)–\(H\) or \(H\)–\(J\) already), 3.6 (\(G\)–\(J\)), 3.7 (\(G\)–\(I\) or \(I\)–\(J\)), 3.9 (\(B\)–\(E\)) | M1 A1 A1 | M1 for using Kruskal's method; A1 correct first several edges; A1 all correct order rejecting cycle-forming edges |
| Length of MST | B1 | Correct total length (follow through) |
| Correct diagram of MST | B1 | Fully correct drawing |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Starting from \(A\): final edge added is \(B\)–\(E\) (3.9) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Starting from \(F\): final edge added is \(B\)–\(E\) (3.9) | B1 |
# Question 3:
## Part (a)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Edges selected in order: $B$–$C$ (2.5), $H$–$J$ (2.9), $E$–$F$ or $D$–$E$ (wait — $E$–$G$: 2.3), then $A$–$B$ or next smallest… Correct order: 2.3 ($E$–$G$), 2.5 ($A$–$B$), 2.9 ($H$–$J$), 3.1 ($A$–$C$), 3.2 ($A$–$D$ or $C$–$D$), 3.4 ($G$–$H$ or $H$–$J$ already), 3.6 ($G$–$J$), 3.7 ($G$–$I$ or $I$–$J$), 3.9 ($B$–$E$) | M1 A1 A1 | M1 for using Kruskal's method; A1 correct first several edges; A1 all correct order rejecting cycle-forming edges |
| Length of MST | B1 | Correct total length (follow through) |
| Correct diagram of MST | B1 | Fully correct drawing |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Starting from $A$: final edge added is $B$–$E$ (3.9) | B1 | |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Starting from $F$: final edge added is $B$–$E$ (3.9) | B1 | |3 The following network shows the lengths, in miles, of roads connecting ten villages, $A , B , C , \ldots , J$.\\
\includegraphics[max width=\textwidth, alt={}, center]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-06_899_1458_397_285}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the network.
\item Find the length of your minimum spanning tree.
\item Draw your minimum spanning tree.
\end{enumerate}\item Prim's algorithm from different starting points produces the same minimum spanning tree. State the final edge that would be added to complete the minimum spanning tree if the starting point were:
\begin{enumerate}[label=(\roman*)]
\item $A$;
\item $F$.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2013 Q3 [9]}}