| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 5 |
| 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: start at D, repeatedly select the minimum edge connecting the tree to a new vertex, and sum the costs. Requires careful execution but no problem-solving or insight beyond the algorithm itself. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | \(E\) | \(F\) | |
| A | - | 130 | 190 | 155 | 140 | 125 |
| B | 130 | - | 215 | 200 | 190 | 170 |
| C | 190 | 215 | - | 110 | 180 | 100 |
| D | 155 | 200 | 110 | - | 70 | 45 |
| E | 140 | 190 | 180 | 70 | - | 75 |
| F | 125 | 170 | 100 | 45 | 75 | - |
| Answer | Marks | Guidance |
|---|---|---|
| order: 5, 6, 4, 1, 3, 2 giving \(B \xrightarrow{130} A \xrightarrow{125} F \xrightarrow{100} C\) with \(D \xrightarrow{45} F\) and \(D \xrightarrow{70} E\) lowest cost = £470 | M2 A2, A1 | (5) |
| order: 5, 6, 4, 1, 3, 2 giving $B \xrightarrow{130} A \xrightarrow{125} F \xrightarrow{100} C$ with $D \xrightarrow{45} F$ and $D \xrightarrow{70} E$ lowest cost = £470 | M2 A2, A1 | (5) |\begin{enumerate}
\item This question should be answered on the sheet provided.
\end{enumerate}
A College wants to connect the computerised registration equipment at its six sites, $A$ to $F$. The table below shows the cost, in pounds, of connecting any two of the sites.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & $E$ & $F$ \\
\hline
A & - & 130 & 190 & 155 & 140 & 125 \\
\hline
B & 130 & - & 215 & 200 & 190 & 170 \\
\hline
C & 190 & 215 & - & 110 & 180 & 100 \\
\hline
D & 155 & 200 & 110 & - & 70 & 45 \\
\hline
E & 140 & 190 & 180 & 70 & - & 75 \\
\hline
F & 125 & 170 & 100 & 45 & 75 & - \\
\hline
\end{tabular}
\end{center}
Starting at $D$, use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. Hence, state the lowest cost of connecting all the sites.\\
(5 marks)\\
\hfill \mbox{\textit{Edexcel D1 Q1 [5]}}