| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Identify specific edge in algorithm |
| Difficulty | Moderate -0.8 This is a straightforward application of standard MST algorithms (Prim's and Kruskal's) with clear instructions and a small graph (7 vertices). Part (b) requires understanding algorithm mechanics but involves minimal problem-solving since the MST is already found in part (a). The question is easier than average A-level maths as it's purely algorithmic execution with no conceptual challenges or proof required. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Danish ( \(\boldsymbol { D }\) ) | English ( \(\boldsymbol { E }\) ) | French (F) | German ( \(G\) ) | Hungarian (H) | Italian (I) | Spanish \(\boldsymbol { ( } \boldsymbol { S } \boldsymbol { ) }\) | |
| Danish (D) | - | 120 | 140 | 80 | 170 | 140 | 140 |
| English ( \(\boldsymbol { E }\) ) | 120 | - | 70 | 80 | 130 | 130 | 110 |
| French (F) | 140 | 70 | - | 90 | 190 | 85 | 90 |
| German ( \(G\) ) | 80 | 80 | 90 | - | 110 | 100 | 100 |
| Hungarian (H) | 170 | 130 | 190 | 110 | - | 140 | 150 |
| Italian (I) | 140 | 130 | 85 | 100 | 140 | - | 60 |
| Spanish ( \(\boldsymbol { S }\) ) | 140 | 110 | 90 | 100 | 150 | 60 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Start at \(E\); select \(EF = 70\) | B1 | First edge correct |
| Select \(EG = 80\) | M1 | Correct application of Prim's from table |
| Select \(GD = 80\); \(FI = 85\); \(IS = 60\); \(EH = 130\) | A1 A1 A1 | One mark per correct edge in order (allow one error) |
| All 6 edges selected correctly in valid Prim's order | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Length \(= 70+80+80+85+60+130 = 505\) euros | B1 | Follow through from their MST |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct tree drawn with 6 edges connecting all 7 nodes | B1 B1 | B1 for correct shape/structure; B1 for all weights correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Starting from \(H\): final two edges added are \(EH\) (or \(GH\)) and \(GD\) (or equivalent last two in Prim's from \(H\)) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Kruskal's: final two edges added are \(EG=80\) and \(GD=80\) (the two heaviest edges in the MST) | B1 B1 |
# Question 2:
## Part (a)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Start at $E$; select $EF = 70$ | B1 | First edge correct |
| Select $EG = 80$ | M1 | Correct application of Prim's from table |
| Select $GD = 80$; $FI = 85$; $IS = 60$; $EH = 130$ | A1 A1 A1 | One mark per correct edge in order (allow one error) |
| All 6 edges selected correctly in valid Prim's order | A1 | |
## Part (a)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Length $= 70+80+80+85+60+130 = 505$ euros | B1 | Follow through from their MST |
## Part (a)(iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct tree drawn with 6 edges connecting all 7 nodes | B1 B1 | B1 for correct shape/structure; B1 for all weights correct |
## Part (b)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Starting from $H$: final two edges added are $EH$ (or $GH$) and $GD$ (or equivalent last two in Prim's from $H$) | B1 | |
## Part (b)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Kruskal's: final two edges added are $EG=80$ and $GD=80$ (the two heaviest edges in the MST) | B1 B1 | |
---2 A document which is currently written in English is to be translated into six other European Union languages. The cost of translating a document varies, as it is harder to find translators for some languages.
The costs, in euros, are shown in the table below.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item On the table below, showing the order in which you select the edges, use Prim's algorithm, starting from $E$, to find a minimum spanning tree for the graph connecting $D , E , F , G , H , I$ and $S$.
\item Find the length of your minimum spanning tree.
\item Draw your minimum spanning tree.
\end{enumerate}\item It is given that the graph has a unique minimum spanning tree.
State the final two edges that would be added to complete the minimum spanning tree in the case where:
\begin{enumerate}[label=(\roman*)]
\item Prim's algorithm starting from $H$ is used;
\item Kruskal's algorithm is used.
\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Answer space for question 2}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& Danish ( $\boldsymbol { D }$ ) & English ( $\boldsymbol { E }$ ) & French (F) & German ( $G$ ) & Hungarian (H) & Italian (I) & Spanish $\boldsymbol { ( } \boldsymbol { S } \boldsymbol { ) }$ \\
\hline
Danish (D) & - & 120 & 140 & 80 & 170 & 140 & 140 \\
\hline
English ( $\boldsymbol { E }$ ) & 120 & - & 70 & 80 & 130 & 130 & 110 \\
\hline
French (F) & 140 & 70 & - & 90 & 190 & 85 & 90 \\
\hline
German ( $G$ ) & 80 & 80 & 90 & - & 110 & 100 & 100 \\
\hline
Hungarian (H) & 170 & 130 & 190 & 110 & - & 140 & 150 \\
\hline
Italian (I) & 140 & 130 & 85 & 100 & 140 & - & 60 \\
\hline
Spanish ( $\boldsymbol { S }$ ) & 140 & 110 & 90 & 100 & 150 & 60 & - \\
\hline
\end{tabular}
\end{center}
\end{table}
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2014 Q2 [11]}}