| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | State number of edges formula |
| Difficulty | Easy -1.8 Part (a) tests direct recall of the fundamental MST formula (n-1 edges for n vertices), which is definitional knowledge requiring no problem-solving. Part (b) applies Kruskal's algorithm mechanically to a small network—a standard textbook exercise in Decision Maths with clear procedural steps and no conceptual challenges. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 9 edges | B1 | For a spanning tree on 10 vertices |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(n-1\) edges | B1 | General formula |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Edges selected in order: EF=8, JI=11.5, BC=8.5, GF=20.5... sorted list attempted | M1 | Must sort edges or show Kruskal's process |
| EF=8, JI=11.5, BC=8.5, AJ=15 or similar correct selections | A1 | Correct first selections |
| Correctly rejecting edges that form cycles | M1 | e.g. reject IH=18 if cycle formed |
| 7 further correct edges selected | A1 | |
| All 9 edges correct | A1 | Complete correct MST |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Total length stated correctly (sum of 9 selected edges) | B1 ft | Follow through from (b)(i) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Tree drawn with correct structure | B1 | Correct vertices connected |
| All 9 edges correctly shown | B1 | Must match answer to (b)(i) |
# Question 3:
## Part (a)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 9 edges | B1 | For a spanning tree on 10 vertices |
## Part (a)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $n-1$ edges | B1 | General formula |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Edges selected in order: EF=8, JI=11.5, BC=8.5, GF=20.5... sorted list attempted | M1 | Must sort edges or show Kruskal's process |
| EF=8, JI=11.5, BC=8.5, AJ=15 or similar correct selections | A1 | Correct first selections |
| Correctly rejecting edges that form cycles | M1 | e.g. reject IH=18 if cycle formed |
| 7 further correct edges selected | A1 | |
| All 9 edges correct | A1 | Complete correct MST |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Total length stated correctly (sum of 9 selected edges) | B1 ft | Follow through from (b)(i) |
## Part (b)(iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Tree drawn with correct structure | B1 | Correct vertices connected |
| All 9 edges correctly shown | B1 | Must match answer to (b)(i) |3
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item State the number of edges in a minimum spanning tree for a network with 10 vertices.
\item State the number of edges in a minimum spanning tree for a network with $n$ vertices.
\end{enumerate}\item The following network has 10 vertices: $A , B , \ldots , J$. The number on each edge represents the distance between a pair of adjacent vertices.\\
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-06_921_1710_717_150}
\begin{enumerate}[label=(\roman*)]
\item Use Kruskal's algorithm to find the minimum spanning tree for the network.
\item State the length of your minimum spanning tree.
\item Draw your minimum spanning tree.\\
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-07_38_118_440_159}\\
\includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-07_40_118_529_159}
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2009 Q3 [10]}}