| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Define tree terminology |
| Difficulty | Easy -1.8 This is a straightforward recall and routine application question from Decision Maths. Part (a) asks for textbook definitions of basic graph theory terms, part (b) requires naming Kruskal's algorithm, and part (c) is a standard Prim's algorithm application with clear tabular data. No problem-solving insight or novel reasoning is required—purely procedural execution of a learned algorithm. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Cambridge | London | Norwich | Oxford | Portsmouth | Salisbury | York | |
| Cambridge (C) | - | 60 | 62 | 81 | 132 | 139 | 156 |
| London (L) | 60 | - | 116 | 56 | 74 | 88 | 211 |
| Norwich (N) | 62 | 116 | - | 144 | 204 | 201 | 181 |
| Oxford (O) | 81 | 56 | 144 | - | 84 | 63 | 184 |
| Portsmouth (P) | 132 | 74 | 204 | 84 | - | 43 | 269 |
| Salisbury (S) | 139 | 88 | 201 | 63 | 43 | - | 248 |
| York (Y) | 156 | 211 | 181 | 184 | 269 | 248 | - |
| Answer | Marks |
|---|---|
| (i) All pairs of vertices connected by a path, but not describing complete graph | B1 |
| (ii) No cycles | B1 |
| (iii) All nodes connected (accept definition of minimum spanning tree) | B1 |
| Answer | Marks |
|---|---|
| Kruskal's (algorithm) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| L-O 56, L-C 60, C-N 62, O-S 63, S-P 43, C-Y 156 | M1 | Using Prim's: first 2 correct |
| Next 2 correct | A1 | |
| Complete and correct | A1 | |
| Total length 440 (miles) | A1 = B1 |
| Answer | Marks |
|---|---|
| Tree correct (Y-C-N, C-O-L, O-S-P structure) | B1 |
# Question 2:
## Part (a)
| (i) All pairs of vertices connected by a path, but not describing complete graph | B1 | |
| (ii) No cycles | B1 | |
| (iii) All nodes connected (accept definition of minimum spanning tree) | B1 | |
## Part (b)
| Kruskal's (algorithm) | B1 | |
## Part (c)(i)
| L-O 56, L-C 60, C-N 62, O-S 63, S-P 43, C-Y 156 | M1 | Using Prim's: first 2 correct |
| Next 2 correct | A1 | |
| Complete and correct | A1 | |
| Total length 440 (miles) | A1 = B1 | |
## Part (c)(ii)
| Tree correct (Y-C-N, C-O-L, O-S-P structure) | B1 | |
---2. Prim's algorithm finds a minimum spanning tree for a connected graph.
\begin{enumerate}[label=(\alph*)]
\item Explain the terms
\begin{enumerate}[label=(\roman*)]
\item connected graph,
\item tree,
\item spanning tree.
\end{enumerate}\item Name an alternative algorithm for finding a minimum spanning tree.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& Cambridge & London & Norwich & Oxford & Portsmouth & Salisbury & York \\
\hline
Cambridge (C) & - & 60 & 62 & 81 & 132 & 139 & 156 \\
\hline
London (L) & 60 & - & 116 & 56 & 74 & 88 & 211 \\
\hline
Norwich (N) & 62 & 116 & - & 144 & 204 & 201 & 181 \\
\hline
Oxford (O) & 81 & 56 & 144 & - & 84 & 63 & 184 \\
\hline
Portsmouth (P) & 132 & 74 & 204 & 84 & - & 43 & 269 \\
\hline
Salisbury (S) & 139 & 88 & 201 & 63 & 43 & - & 248 \\
\hline
York (Y) & 156 & 211 & 181 & 184 & 269 & 248 & - \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{table}
Figure 2 shows the distances by road, in miles, between seven cities.
\item \begin{enumerate}[label=(\roman*)]
\item Use Prim's algorithm, starting at London, to find the minimum spanning tree for these cities. You must clearly state the order in which you selected the edges of your tree, and the weight of the final tree.
\item Draw your tree using the vertices given in Diagram 2 in the answer book.\\
(5)
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2010 Q2 [9]}}