| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Kruskal's algorithm |
| Difficulty | Moderate -0.8 This is a straightforward application of Kruskal's algorithm, a standard D1 topic requiring systematic edge selection in ascending order and cycle checking. The multi-part structure (apply algorithm, state total, identify alternative MST) adds some marks but involves routine procedural work with no novel problem-solving or proof required. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Edges selected in order: \(DE=6\), \(AC=8\), \(AD=10\) (or \(CD=10\)), \(CF=16\) (if \(CD\) not already chosen), \(EG=21\) | M1 | Correct process of selecting edges in ascending order |
| Reject any edge forming a cycle | M1 | Cycles correctly rejected |
| Edges: \(DE(6),\ AC(8),\ AD(10),\ DF(10\ \text{or }CF=16),\ EG(21)\), \(CF(16)\) | A1 A1 | Correct edges selected |
| Correct minimum spanning tree identified | A1 | All 6 edges correct, connecting all 7 vertices |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(6+8+10+10+16+21 = 71\) miles | B1 | cao, follow through from (a) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| First MST drawn correctly | B1 | Correct first tree |
| Second MST drawn correctly (differs by swapping \(CD=10\) for \(AD=10\) or equivalent tie-break edge) | B1 | Correct second tree |
| Both trees clearly drawn and distinct | B1 | Both correct and different |
# Question 3(a): Kruskal's Algorithm
| Answer | Marks | Guidance |
|--------|-------|----------|
| Edges selected in order: $DE=6$, $AC=8$, $AD=10$ (or $CD=10$), $CF=16$ (if $CD$ not already chosen), $EG=21$ | M1 | Correct process of selecting edges in ascending order |
| Reject any edge forming a cycle | M1 | Cycles correctly rejected |
| Edges: $DE(6),\ AC(8),\ AD(10),\ DF(10\ \text{or }CF=16),\ EG(21)$, $CF(16)$ | A1 A1 | Correct edges selected |
| Correct minimum spanning tree identified | A1 | All 6 edges correct, connecting all 7 vertices |
# Question 3(b): Length of MST
| Answer | Marks | Guidance |
|--------|-------|----------|
| $6+8+10+10+16+21 = 71$ miles | B1 | cao, follow through from (a) |
# Question 3(c): Two Minimum Spanning Trees
| Answer | Marks | Guidance |
|--------|-------|----------|
| First MST drawn correctly | B1 | Correct first tree |
| Second MST drawn correctly (differs by swapping $CD=10$ for $AD=10$ or equivalent tie-break edge) | B1 | Correct second tree |
| Both trees clearly drawn and distinct | B1 | Both correct and different |3 The following network shows the roads connecting seven villages, $A , B , C , \ldots , G$. The number on each edge represents the length, in miles, between a pair of villages.\\
\includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-06_978_1108_443_466}
\begin{enumerate}[label=(\alph*)]
\item Use Kruskal's algorithm to find a minimum spanning tree for the network. (5 marks)
\item State the length of your minimum spanning tree.
\item There are two minimum spanning trees for this network. Draw both of these minimum spanning trees.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2012 Q3 [9]}}