| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2003 |
| Session | November |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Define tree terminology |
| Difficulty | Easy -1.8 This is a straightforward recall and application question on basic MST algorithms. Part (a) requires memorized definitions, part (b) is simple recall of algorithm differences, part (c) is routine application of Kruskal's algorithm, and part (d) is a simple modification. No problem-solving insight or novel reasoning required—purely procedural work typical of Decision Maths questions. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| i. A connected graph with no cycles, loops or multiple edges | B1 | |
| ii. A tree that includes all vertices | B1 | |
| iii. A spanning tree of minimum total length | B1 | (3) |
| Answer | Marks | Guidance |
|---|---|---|
| In Kruskal the shortest arc is added (unless it completes a cycle), in Prim the nearest unattached vertex is added. There is no need to check for cycles when using Prim, but there is when using Kruskal. In Prim the tree always "grows" in a connected fashion. Kruskal starts with the shortest edge, Prim with any vertex. | B1 | (1) |
| Answer | Marks | Guidance |
|---|---|---|
| BH, NF, HN, HA, BE, NC; length \(= 48\) | M1, A1, A1 | |
| Diagram showing spanning tree with edges labelled 5, 7, 8, 6, 9, 13 | A1 | (4) |
| Answer | Marks | Guidance |
|---|---|---|
| Diagram showing edges 50, 80, 70, 60, 130 | B1 | |
| New cable \(= 390\text{m}\) | M1, A1 | (3) |
# Question 6:
## Part (a)
i. A connected graph with no cycles, loops or multiple edges | B1 |
ii. A tree that includes all vertices | B1 |
iii. A spanning tree of minimum total length | B1 | (3)
## Part (b)
In Kruskal the shortest arc is added (unless it completes a cycle), in Prim the nearest unattached vertex is added. There is no need to check for cycles when using Prim, but there is when using Kruskal. In Prim the tree always "grows" in a connected fashion. Kruskal starts with the shortest edge, Prim with any vertex. | B1 | (1)
## Part (c)
BH, NF, HN, HA, BE, NC; length $= 48$ | M1, A1, A1 |
Diagram showing spanning tree with edges labelled 5, 7, 8, 6, 9, 13 | A1 | (4)
## Part (d)
Diagram showing edges 50, 80, 70, 60, 130 | B1 |
New cable $= 390\text{m}$ | M1, A1 | (3)
**Total: 11 marks**
---6. (a) Define the terms
\begin{enumerate}[label=(\roman*)]
\item tree,
\item spanning tree,
\item minimum spanning tree.\\
(3)\\
(b) State one difference between Kruskal's algorithm and Prim's algorithm, to find a minimum spanning tree.\\
(1)
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-08_894_1529_920_322}
\end{center}
\end{figure}
(c) Use Kruskal's algorithm to find the minimum spanning tree for the network shown in Fig. 4. State the order in which you included the arcs. Draw the minimum spanning tree in Diagram 1 in the answer book and state its length.\\
(4)
\section*{Figure 5}
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-09_887_1536_342_258}
\end{center}
Figure 5 models a car park. Currently there are two pay-stations, one at $E$ and one at $N$. These two are linked by a cable as shown. New pay-stations are to be installed at $B , H , A , F$ and $C$. The number on each arc represents the distance between the pay-stations in metres. All of the pay-stations need to be connected by cables, either directly or indirectly. The current cable between $E$ and $N$ must be included in the final network. The minimum amount of new cable is to be used.\\
(d) Using your answer to part (c), or otherwise, determine the minimum amount of new cable needed. Use Diagram 2 to show where these cables should be installed. State the minimum amount of new cable needed.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2003 Q6 [11]}}