| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm in matrix form |
| Difficulty | Moderate -0.8 This is a straightforward application of Prim's algorithm from a matrix, which is a standard algorithmic procedure in D1. Students follow a mechanical process (select smallest edge from connected vertices, repeat), requiring careful bookkeeping but no problem-solving insight or novel thinking. Part (b) simply repeats the algorithm with one vertex removed. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) | \(\boldsymbol { F }\) | \(\boldsymbol { G }\) | \(\boldsymbol { H }\) | |
| \(\boldsymbol { A }\) | - | 15 | 10 | 12 | 16 | 11 | 14 | 17 |
| \(\boldsymbol { B }\) | 15 | - | 15 | 14 | 15 | 16 | 16 | 15 |
| \(\boldsymbol { C }\) | 10 | 15 | - | 11 | 10 | 12 | 14 | 9 |
| \(\boldsymbol { D }\) | 12 | 14 | 11 | - | 11 | 12 | 14 | 12 |
| \(\boldsymbol { E }\) | 16 | 15 | 10 | 11 | - | 13 | 15 | 14 |
| \(\boldsymbol { F }\) | 11 | 16 | 12 | 12 | 13 | - | 14 | 8 |
| G | 14 | 16 | 14 | 14 | 15 | 14 | - | 13 |
| \(\boldsymbol { H }\) | 17 | 15 | 9 | 12 | 14 | 8 | 13 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Select \(AC = 10\) | B1 | First edge correct |
| Select \(CE = 10\) or \(CD = 11\) | M1 | Correct application of Prim's |
| Correct sequence: \(AC\), \(CE\), \(CD\), \(AF\) or \(CF\), \(FH\), \(DE\) or \(DG\) or similar correct order | A1 | Evidence of algorithm being applied |
| All 7 edges of MST correctly selected | A1 | Full correct set of edges |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct tree drawn with 8 nodes, 7 edges matching selected edges | B1 | Correct structure |
| Edges correctly labelled with weights | B1 | All weights correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Minimum total cost \(= 93\) pence | B1 | Correct sum of MST edges |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Remove \(H\) and any edges incident to \(H\); find new MST for remaining 7 nodes | M1 | Correct method of removing \(H\) |
| New minimum total cost \(= 89\) pence | A1 | Correct answer |
# Question 3:
## Part (a)(i):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Select $AC = 10$ | B1 | First edge correct |
| Select $CE = 10$ or $CD = 11$ | M1 | Correct application of Prim's |
| Correct sequence: $AC$, $CE$, $CD$, $AF$ or $CF$, $FH$, $DE$ or $DG$ or similar correct order | A1 | Evidence of algorithm being applied |
| All 7 edges of MST correctly selected | A1 | Full correct set of edges |
## Part (a)(ii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct tree drawn with 8 nodes, 7 edges matching selected edges | B1 | Correct structure |
| Edges correctly labelled with weights | B1 | All weights correct |
## Part (a)(iii):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Minimum total cost $= 93$ pence | B1 | Correct sum of MST edges |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Remove $H$ and any edges incident to $H$; find new MST for remaining 7 nodes | M1 | Correct method of removing $H$ |
| New minimum total cost $= 89$ pence | A1 | Correct answer |3 A group of eight friends, $A , B , C , D , E , F , G$ and $H$, keep in touch by sending text messages. The cost, in pence, of sending a message between each pair of friends is shown in the following table.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
& $\boldsymbol { A }$ & $\boldsymbol { B }$ & $\boldsymbol { C }$ & $\boldsymbol { D }$ & $\boldsymbol { E }$ & $\boldsymbol { F }$ & $\boldsymbol { G }$ & $\boldsymbol { H }$ \\
\hline
$\boldsymbol { A }$ & - & 15 & 10 & 12 & 16 & 11 & 14 & 17 \\
\hline
$\boldsymbol { B }$ & 15 & - & 15 & 14 & 15 & 16 & 16 & 15 \\
\hline
$\boldsymbol { C }$ & 10 & 15 & - & 11 & 10 & 12 & 14 & 9 \\
\hline
$\boldsymbol { D }$ & 12 & 14 & 11 & - & 11 & 12 & 14 & 12 \\
\hline
$\boldsymbol { E }$ & 16 & 15 & 10 & 11 & - & 13 & 15 & 14 \\
\hline
$\boldsymbol { F }$ & 11 & 16 & 12 & 12 & 13 & - & 14 & 8 \\
\hline
G & 14 & 16 & 14 & 14 & 15 & 14 & - & 13 \\
\hline
$\boldsymbol { H }$ & 17 & 15 & 9 & 12 & 14 & 8 & 13 & - \\
\hline
\end{tabular}
\end{center}
One of the group wishes to pass on a piece of news to all the other friends, either by a direct text or by the message being passed on from friend to friend, at the minimum total cost.
\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 table.
\item Draw your minimum spanning tree.
\item Find the minimum total cost.
\end{enumerate}\item Person $H$ leaves the group. Find the new minimum total cost.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2011 Q3 [9]}}