| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | MST with edges pre-included |
| Difficulty | Moderate -0.5 This is a standard D1 MST question requiring routine application of Prim's and Kruskal's algorithms with straightforward bookkeeping. Part (c) adds a minor twist with pre-included edges, but this is a common textbook variation. The algorithms are mechanical procedures requiring no problem-solving insight, making this easier than average A-level maths questions which typically involve more conceptual understanding or multi-step reasoning. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| AB, BC, CF, CE; FG, AD; EH, HI | M1; 1A1; 2A1 (3) | a1M1: First four arcs (AB, BC, CF, CE) correctly chosen, or first five nodes (ABCFE) correctly chosen in order. If any rejections seen at any point then M1 (max) only. a1A1: First six arcs correctly chosen (AB, BC, CF, CE, FG, AD), or all nodes in order (ABCFEGDHI). a2A1: CSO (must be arcs). |
| Answer | Marks | Guidance |
|---|---|---|
| £191 | B1 (1) | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| CF, reject CE, AB, FG; {AD, reject AC}, reject DG, {reject BE, reject DF}, EH, reject FH, HI (Note BC and EF are already in the tree) | M1; 1A1; 2A1 (5) | ci1M1: Kruskal's — first three arcs (CF, AB, FG) correctly chosen and at least one rejection seen at some point. ci1A1: All arcs in tree selected correctly at correct time (CF, AB, FG, AD, EH, HI). Ignore any reference to BC and EF. ci2A1: CSO including all rejections correct and at the correct time. |
| Answer | Marks | Guidance |
|---|---|---|
| e.g. Prim cannot be used since with Prim the tree 'grows' in a connected fashion; e.g. Kruskal can build its tree from disconnected fragments | B2,1,0 | cii1B1: Partially correct answer — e.g. an indication that the arcs (BC and EF) are not connected or any mention of the tree being (initially) disconnected. cii2B1: Fully correct answer (so either Kruskal allows a tree to be formed from initially unconnected arcs or Prim requires the arcs/tree to be connected at all times). |
| Answer | Marks | Guidance |
|---|---|---|
| £147 | B1 (1) | CAO |
# Question 2:
## Part (a)
AB, BC, CF, CE; FG, AD; EH, HI | M1; 1A1; 2A1 **(3)** | a1M1: First four arcs (AB, BC, CF, CE) correctly chosen, or first five nodes (ABCFE) correctly chosen in order. If any rejections seen at any point then M1 (max) only. a1A1: First six arcs correctly chosen (AB, BC, CF, CE, FG, AD), or all nodes in order (ABCFEGDHI). a2A1: CSO (must be arcs).
## Part (b)
£191 | B1 **(1)** | CAO
## Part (c)(i)
CF, reject CE, AB, FG; {AD, reject AC}, reject DG, {reject BE, reject DF}, EH, reject FH, HI (Note BC and EF are already in the tree) | M1; 1A1; 2A1 **(5)** | ci1M1: Kruskal's — first three arcs (CF, AB, FG) correctly chosen and at least one rejection seen at some point. ci1A1: All arcs in tree selected correctly at correct time (CF, AB, FG, AD, EH, HI). Ignore any reference to BC and EF. ci2A1: CSO including all rejections correct and at the correct time.
## Part (c)(ii)
e.g. Prim cannot be used since with Prim the tree 'grows' in a connected fashion; e.g. Kruskal can build its tree from disconnected fragments | B2,1,0 | cii1B1: Partially correct answer — e.g. an indication that the arcs (BC and EF) are not connected **or** any mention of the tree being (initially) disconnected. cii2B1: Fully correct answer (so either Kruskal allows a tree to be formed from initially unconnected arcs or Prim requires the arcs/tree to be connected at all times).
## Part (d)
£147 | B1 **(1)** | CAO
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
\item State the minimum cost of connecting the alarm systems in the nine buildings.
It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
\item \begin{enumerate}[label=(\roman*)]
\item Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
\item Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case.
Since arcs BC and EF already exist, there is no cost for these connections.
\end{enumerate}\item State the new minimum cost of connecting the nine buildings.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2014 Q2 [10]}}