| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Compare Prim's and Kruskal's algorithms |
| Difficulty | Moderate -0.8 This is a straightforward recall and application question on standard D1 algorithms. Part (a) requires memorized differences between two algorithms (2 marks), while part (b) involves mechanical application of both algorithms to a small network with no problem-solving or insight required—purely procedural execution of learned methods. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Other correct statements also get credit. | B 2, 1, 0 | (2 marks) |
| (b)(i) e.g. AC, CF, FD, DE, DG, AB. | M1, A1, A1 | (3 marks) |
| Answer | Marks | Guidance |
|---|---|---|
| (b)(ii) CF, DE, DF, not CD, not EF, DG, not FG, not EG, AC, not AD, AB. [18, 19, 20, not 21, not 21, 22, not 23, not 24, 25, not 26, 27] | M1, A1, A1 | (3 marks) |
**(a)** e.g.
- Prims starts with any vertex, Kruskal starts with the shortest arc.
- It is not necessary to check for cycles when using Prim.
- Prims adds nodes to the growing tree. Kruskal adds arcs.
- The tree 'grows' in a connected fashion when using Prim.
- Prim can be used when data in a matrix form.
Other correct statements also get credit. | B 2, 1, 0 | (2 marks) |
**(b)(i)** e.g. AC, CF, FD, DE, DG, AB. | M1, A1, A1 | (3 marks) |
**Guidance:** 1M1: Prim's algorithm – first three arcs chosen correctly, in order, or first four nodes chosen correctly, in order. 1A1: First five arcs chosen correctly; all 7 nodes chosen correctly, in order. 2A1: All correct and arcs chosen in correct order.
**(b)(ii)** CF, DE, DF, not CD, not EF, DG, not FG, not EG, AC, not AD, AB. [18, 19, 20, not 21, not 21, 22, not 23, not 24, 25, not 26, 27] | M1, A1, A1 | (3 marks) |
**Guidance:** 1M1: Kruskal's algorithm – first 4 arcs selected chosen correctly. 2A1: All six non-rejected arcs chosen correctly. 2A1: All rejections correct and in correct order and at correct time.
**Total for Q4: 8 marks**
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-4_653_1257_248_404}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item State two differences between Kruskal's algorithm and Prim's algorithm for finding a minimum spanning tree.\\
(2)
\item Listing the arcs in the order that you consider them, find a minimum spanning tree for the network in Figure 4, using
\begin{enumerate}[label=(\roman*)]
\item Prim's algorithm,
\item Kruskal's algorithm.\\
(6)
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2008 Q4 [8]}}