| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2002 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm in matrix form |
| Difficulty | Moderate -0.8 This is a straightforward application of Prim's algorithm from a distance table, requiring systematic selection of minimum edges and basic knowledge that an MST has n-1 edges for n vertices. The algorithm is mechanical with no problem-solving insight needed, making it easier than average A-level questions, though the multi-part structure and table work prevent it from being trivial. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | |
| \(A\) | -- | 10 | 12 | 13 | 20 | 9 |
| \(B\) | 10 | -- | 7 | 15 | 11 | 7 |
| \(C\) | 12 | 7 | -- | 11 | 18 | 3 |
| \(D\) | 13 | 15 | 11 | -- | 27 | 8 |
| \(E\) | 20 | 11 | 18 | 27 | -- | 18 |
| \(F\) | 9 | 7 | 3 | 8 | 18 | -- |
| Answer | Marks |
|---|---|
| Method: Choose vertex nearest to A and add to tree. Choose vertex nearest to any vertex on tree. Repeat (set step until all vertices in cluster). | M1, A1 |
| Answer | Marks |
|---|---|
| Order of arc selection: AF, FC, FB or BC, FD, EB | M1, A1, (4) |
| Answer | Marks |
|---|---|
| Not unique - gives other one, or convincing explanation | B1, B1, B1, (1) |
| Answer | Marks |
|---|---|
| Number of edges = 7 - 1 = 6 | B1 |
| Answer | Marks |
|---|---|
| Number of vertices = n + 1 | B1, (2) |
## (i)(a)
Method: Choose vertex nearest to A and add to tree. Choose vertex nearest to any vertex on tree. Repeat (set step until all vertices in cluster). | M1, A1 |
## (i)(b)
Order of arc selection: AF, FC, FB or BC, FD, EB | M1, A1, (4) |
## (i)(c)
Not unique - gives other one, or convincing explanation | B1, B1, B1, (1) |
## (ii)(a)
Number of edges = 7 - 1 = 6 | B1 |
## (ii)(b)
Number of vertices = n + 1 | B1, (2) |
---\begin{enumerate}[label=(\roman*)]
\item
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
& $A$ & $B$ & $C$ & $D$ & $E$ & $F$ \\
\hline
$A$ & -- & 10 & 12 & 13 & 20 & 9 \\
\hline
$B$ & 10 & -- & 7 & 15 & 11 & 7 \\
\hline
$C$ & 12 & 7 & -- & 11 & 18 & 3 \\
\hline
$D$ & 13 & 15 & 11 & -- & 27 & 8 \\
\hline
$E$ & 20 & 11 & 18 & 27 & -- & 18 \\
\hline
$F$ & 9 & 7 & 3 & 8 & 18 & -- \\
\hline
\end{tabular}
\end{center}
The table shows the distances, in metres, between six nodes $A$, $B$, $C$, $D$, $E$, and $F$ of a network.
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at $A$, to solve the minimum connector problem for this table of distances. Explain your method and indicate the order in which you selected the edges. [4]
\item Draw your minimum spanning tree and find its total length. [2]
\item State whether your minimum spanning tree is unique. Justify your answer. [1]
\end{enumerate}
\item A connected network $N$ has seven vertices.
\begin{enumerate}[label=(\alph*)]
\item State the number of edges in a minimum spanning tree for $N$. [1]
\end{enumerate}
A minimum spanning tree for a connected network has $n$ edges.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumii}{1}
\item State the number of vertices in the network. [1]
\end{enumerate}
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2002 Q3 [9]}}