| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2017 |
| Session | January |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Moderate -0.8 This is a straightforward application of Prim's algorithm from a given starting vertex with a complete distance table. The algorithm is mechanical and requires only careful bookkeeping to select minimum edges at each step. While tedious with 8 vertices, it involves no problem-solving or conceptual insight beyond following the standard procedure taught in D1. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | G | H | |
| A | - | 27 | 51 | 32 | 29 | 23 | 47 | 40 |
| B | 27 | - | 24 | 35 | 20 | 42 | 33 | 28 |
| C | 51 | 24 | - | 37 | 43 | 31 | 26 | 34 |
| D | 32 | 35 | 37 | - | 39 | 45 | 44 | 30 |
| E | 29 | 20 | 43 | 39 | - | 38 | 45 | 55 |
| F | 23 | 42 | 31 | 45 | 38 | - | 53 | 45 |
| G | 47 | 33 | 26 | 44 | 45 | 53 | - | 39 |
| H | 40 | 28 | 34 | 30 | 55 | 45 | 39 | - |
2.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | }
\hline
& A & B & C & D & E & F & G & H \\
\hline
A & - & 27 & 51 & 32 & 29 & 23 & 47 & 40 \\
\hline
B & 27 & - & 24 & 35 & 20 & 42 & 33 & 28 \\
\hline
C & 51 & 24 & - & 37 & 43 & 31 & 26 & 34 \\
\hline
D & 32 & 35 & 37 & - & 39 & 45 & 44 & 30 \\
\hline
E & 29 & 20 & 43 & 39 & - & 38 & 45 & 55 \\
\hline
F & 23 & 42 & 31 & 45 & 38 & - & 53 & 45 \\
\hline
G & 47 & 33 & 26 & 44 & 45 & 53 & - & 39 \\
\hline
H & 40 & 28 & 34 & 30 & 55 & 45 & 39 & - \\
\hline
\end{tabular}
\end{center}
The table represents a network that shows the average journey time, in minutes, between eight towns, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }$ and H .
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must clearly state the order in which you select the edges of your tree.
\item Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.
\item State the weight of the minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2017 Q2 [5]}}