| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm in matrix form |
| Difficulty | Easy -1.3 This is a straightforward application of Prim's algorithm with a small 6-vertex network. Part (a) requires mechanical execution of a standard algorithm taught in D1, parts (b) and (c) are trivial bookkeeping, and part (d) tests basic understanding of why Prim's works. No problem-solving or novel insight required—purely procedural recall below typical A-level difficulty. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks |
|---|---|
| m1, A1, A1 (3) |
| Answer | Marks |
|---|---|
| B1' (1) |
| Answer | Marks |
|---|---|
| B1 (1) |
| Answer | Marks |
|---|---|
| B2, 1, 0 (e) [2] |
## (a)
MB, BE, MD, DC, CA
| m1, A1, A1 (3) |
## (b)
[Diagram showing network with vertices E, A, B, C, D and edges labeled with distances]
| B1' (1) |
## (c)
$170 + 2×0 + 210 + 480 + 100 = 860$
| B1 (1) |
## (d)
(A cycle is formed when an arc is used that connects two vertices already connected to such other in the tree)
From algorithm always selects arcs that bring a vertex not in the tree so a cycle can't happen
| B2, 1, 0 (e) [2] |
---$$\begin{array}{c|c|c|c|c|c}
& M & A & B & C & D & E \\
\hline
M & - & 215 & 170 & 290 & 210 & 305 \\
\hline
A & 215 & - & 275 & 100 & 217 & 214 \\
\hline
B & 170 & 275 & - & 267 & 230 & 200 \\
\hline
C & 290 & 100 & 267 & - & 180 & 220 \\
\hline
D & 210 & 217 & 230 & 180 & - & 245 \\
\hline
E & 305 & 214 & 200 & 220 & 245 & -
\end{array}$$
The table shows the cost, in pounds, of linking five automatic alarm sensors, $A,B,C,D$ and $E$, and the main reception, $M$.
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting from $M$, to find a minimum spanning tree for this table of costs. You must list the arcs that form your tree in the order that they are selected. [3]
\item Draw your tree using the vertices given in Diagram 1 in the answer book. [1]
\item Find the total weight of your tree. [1]
\item Explain why it is not necessary to check for cycles when using Prim's algorithm. [2]
\end{enumerate}
(Total 7 marks)
\hfill \mbox{\textit{Edexcel D1 2007 Q5 [7]}}