| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2017 |
| Session | June |
| Marks | 6 |
| 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 in matrix form, a standard D1 procedure. Students follow a mechanical process: select minimum edge from connected vertices, update the set, repeat. Part (c) tests basic understanding of why Prim's works. While it requires careful execution across multiple steps, it demands no problem-solving insight or novel thinking—purely algorithmic recall and execution, making it easier than average A-level questions. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| S | A | B | C | D | E | F | G | |
| S | - | 150 | 225 | 275 | 135 | 200 | 280 | 255 |
| A | 150 | - | 265 | 300 | 185 | 170 | 385 | 315 |
| B | 225 | 265 | - | 245 | 190 | 155 | 215 | 300 |
| C | 275 | 300 | 245 | - | 250 | 310 | 280 | 275 |
| D | 135 | 185 | 190 | 250 | - | 145 | 205 | 270 |
| E | 200 | 170 | 155 | 310 | 145 | - | 220 | 380 |
| F | 280 | 385 | 215 | 280 | 205 | 220 | - | 250 |
| G | 255 | 315 | 300 | 275 | 270 | 380 | 250 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Scheme | Marks | Guidance |
| (a) SD, DE, AS; BE, DF; BC, FG | M1; A1; A1 | (3) First three arcs correctly chosen in order (SD, DE, AS, …) or first four nodes correctly chosen in order (S, D, E, A, …). If any explicit rejections seen at any point then M1 (max) only. No marks in (a) for list of weights only. Candidates may apply Prim's in matrix form so the order of the nodes may be seen at the top of the matrix – accept {1, 4, -, -, 2, 3, -, -} for the M mark. Allow DS for SD etc. throughout this part |
| (b) Weight of tree = (£)1285; e.g. Prim's algorithm always selects arcs that bring a vertex not in the tree into the tree, so cycles cannot happen. e.g. Prim's algorithm always adds an additional vertex to the tree, so a cycle cannot happen. | B1 | (2) |
| (c) | B1 | (1) |
| 6 marks |
| Answer/Scheme | Marks | Guidance |
|---|---|---|
| (a) SD, DE, AS; BE, DF; BC, FG | M1; A1; A1 | (3) First three arcs correctly chosen in order (SD, DE, AS, …) or first four nodes correctly chosen in order (S, D, E, A, …). If any explicit rejections seen at any point then M1 (max) only. No marks in (a) for list of weights only. Candidates may apply Prim's in matrix form so the order of the nodes may be seen at the top of the matrix – accept {1, 4, -, -, 2, 3, -, -} for the M mark. Allow DS for SD etc. throughout this part |
| (b) Weight of tree = (£)1285; e.g. Prim's algorithm always selects arcs that bring a vertex not in the tree into the tree, so cycles cannot happen. e.g. Prim's algorithm always adds an additional vertex to the tree, so a cycle cannot happen. | B1 | (2) |
| (c) | B1 | (1) |
| | **6 marks** | |
---2.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
& S & A & B & C & D & E & F & G \\
\hline
S & - & 150 & 225 & 275 & 135 & 200 & 280 & 255 \\
\hline
A & 150 & - & 265 & 300 & 185 & 170 & 385 & 315 \\
\hline
B & 225 & 265 & - & 245 & 190 & 155 & 215 & 300 \\
\hline
C & 275 & 300 & 245 & - & 250 & 310 & 280 & 275 \\
\hline
D & 135 & 185 & 190 & 250 & - & 145 & 205 & 270 \\
\hline
E & 200 & 170 & 155 & 310 & 145 & - & 220 & 380 \\
\hline
F & 280 & 385 & 215 & 280 & 205 & 220 & - & 250 \\
\hline
G & 255 & 315 & 300 & 275 & 270 & 380 & 250 & - \\
\hline
\end{tabular}
\end{center}
The table shows the costs, in pounds, of connecting seven computer terminals, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$ and G, to a server, S.
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at S , to find the minimum spanning tree for this table of costs. You must clearly state the order in which you select the edges of your tree.\\
(3)
\item Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. State the minimum cost, in pounds, of connecting the seven computer terminals to the server.
\item Explain why it is not necessary to check for cycles when using Prim's algorithm.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2017 Q2 [6]}}