| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2018 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Define tree terminology |
| Difficulty | Easy -1.8 Part (a) requires pure recall of two standard definitions from Decision Maths, while parts (b) and (c) involve routine application of Prim's algorithm with no problem-solving required. This is a textbook exercise testing basic knowledge and standard procedure execution, making it significantly easier than average A-level questions. |
| Spec | 7.02c Graph terminology: walk, trail, path, cycle, route7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6b51f3a0-0945-4254-8c63-20e1371e9e3a-02_1189_1531_360_267}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item Define the terms
\begin{enumerate}[label=(\roman*)]
\item tree,
\item minimum spanning tree.
\end{enumerate}\item Use Prim's algorithm, starting at A , to find a minimum spanning tree for the network shown in Figure 1. You must clearly state the order in which you select the arcs of the tree.
\item Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2018 Q1 [8]}}