| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 5 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Easy -1.2 This is a straightforward application of Prim's algorithm from a given starting vertex using a distance table. The procedure is entirely algorithmic with no problem-solving required—students simply follow the standard steps they've been taught. While it requires careful bookkeeping across 7 vertices, it's a routine textbook exercise well below average A-level difficulty. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Art | Biology | Chemistry | Drama | English | French | Graphics | |
| Art (A) | - | 61 | 93 | 73 | 50 | 48 | 42 |
| Biology (B) | 61 | - | 114 | 82 | 83 | 63 | 58 |
| Chemistry (C) | 93 | 114 | - | 59 | 94 | 77 | 88 |
| Drama (D) | 73 | 82 | 59 | - | 89 | 104 | 41 |
| English (E) | 50 | 83 | 94 | 89 | - | 91 | 75 |
| French (F) | 48 | 63 | 77 | 104 | 91 | - | 68 |
| Graphics (G) | 42 | 58 | 88 | 41 | 75 | 68 | - |
1.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& Art & Biology & Chemistry & Drama & English & French & Graphics \\
\hline
Art (A) & - & 61 & 93 & 73 & 50 & 48 & 42 \\
\hline
Biology (B) & 61 & - & 114 & 82 & 83 & 63 & 58 \\
\hline
Chemistry (C) & 93 & 114 & - & 59 & 94 & 77 & 88 \\
\hline
Drama (D) & 73 & 82 & 59 & - & 89 & 104 & 41 \\
\hline
English (E) & 50 & 83 & 94 & 89 & - & 91 & 75 \\
\hline
French (F) & 48 & 63 & 77 & 104 & 91 & - & 68 \\
\hline
Graphics (G) & 42 & 58 & 88 & 41 & 75 & 68 & - \\
\hline
\end{tabular}
\end{center}
The table shows the travelling times, in seconds, to walk between seven departments in a college.
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at Art, to find the minimum spanning tree for the network represented by the table. 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.
\item State the weight of the tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2014 Q1 [5]}}