| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2004 |
| Session | January |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply both algorithms and compare |
| Difficulty | Moderate -0.8 This is a standard textbook application of two well-defined algorithms (Kruskal's and Prim's) to find minimum spanning trees. The question requires only mechanical execution of learned procedures with no problem-solving insight or novel reasoning—students simply sort edges and apply the algorithms step-by-step. While it has multiple parts worth 10 marks total, each part is routine algorithmic application, making it easier than average A-level maths questions which typically require some conceptual understanding or multi-step reasoning. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | |
| A | \(-\) | 7 | 3 | \(-\) | 8 | 11 |
| B | 7 | \(-\) | 4 | 2 | \(-\) | 7 |
| C | 3 | 4 | \(-\) | 5 | 9 | \(-\) |
| D | \(-\) | 2 | 5 | \(-\) | 6 | 3 |
| E | 8 | \(-\) | 9 | 6 | \(-\) | \(-\) |
| F | 11 | 7 | \(-\) | 3 | \(-\) | \(-\) |
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
& A & B & C & D & E & F \\
\hline
A & $-$ & 7 & 3 & $-$ & 8 & 11 \\
\hline
B & 7 & $-$ & 4 & 2 & $-$ & 7 \\
\hline
C & 3 & 4 & $-$ & 5 & 9 & $-$ \\
\hline
D & $-$ & 2 & 5 & $-$ & 6 & 3 \\
\hline
E & 8 & $-$ & 9 & 6 & $-$ & $-$ \\
\hline
F & 11 & 7 & $-$ & 3 & $-$ & $-$ \\
\hline
\end{tabular}
\end{center}
The matrix represents a network of roads between six villages $A$, $B$, $C$, $D$, $E$ and $F$. The value in each cell represents the distance, in km, along these roads.
\begin{enumerate}[label=(\alph*)]
\item Show this information on the diagram in the answer book. [2]
\item Use Kruskal's algorithm to determine the minimum spanning tree. State the order in which you include the arcs and the length of the minimum spanning tree. Draw the minimum spanning tree. [5]
\item Starting at $D$, use Prim's algorithm on the matrix given in the answer book to find the minimum spanning tree. State the order in which you include the arcs. [3]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2004 Q6 [10]}}