| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2020 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Define tree terminology |
| Difficulty | Easy -1.8 This is a straightforward recall question testing basic definitions and a standard algorithm application. Part (a) requires memorized definitions, part (b) is a routine application of Kruskal's algorithm with explicit step-by-step guidance, and part (c) is simple transcription. No problem-solving or novel insight required—well below average difficulty. |
| Spec | 7.02c Graph terminology: walk, trail, path, cycle, route7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| A tree is a connected graph with no cycles | B1 | (3) |
| A minimum spanning tree is a tree that contains all vertices. The total length of its arcs is as small as possible | B1 | |
| Kruskal: FJ(11), EG(13), EF(15), EH(17), not GH (18), BC (19), not HJ (20), BD (22), not FH(23), AE (25), BE (29) (not AD, DE, DG, AB, BH) | M1 A1 A1 | (3) |
| [Diagram showing tree with weight 151] | B1 | (2) |
| A tree is a connected graph with no cycles | B1 | (3) |
|---|---|---|
| A minimum spanning tree is a tree that contains all vertices. The total length of its arcs is as small as possible | B1 | |
| Kruskal: FJ(11), EG(13), EF(15), EH(17), not GH (18), BC (19), not HJ (20), BD (22), not FH(23), AE (25), BE (29) (not AD, DE, DG, AB, BH) | M1 A1 A1 | (3) |
| [Diagram showing tree with weight 151] | B1 | (2) |
**Notes for Question 2:**
- **a1B1:** Connected + no cycle(s) (must contain these two points – do not allow 'circle', 'loop' etc. for cycle(s)) – if not using the word 'connected' then allow 'a graph that connects the vertices/nodes' (condone issues with plural or singular e.g. cycle for cycles)
- **a2B1:** Contains all vertices/nodes (must be clear that all vertices (or nodes) are in a MST)
- **a3B1:** Total length of arcs is minimised (must contain the three points regarding weight/length, arcs/edges and minimised/smallest (oe))
- **b1M1:** Kruskal's algorithm - first four arcs (FJ, EG, EF, EH) correctly chosen and at least one rejection seen at some point
- **b1A1:** All arcs in tree selected correctly in the correct order (FJ, EG, EF, EH, BC, BD, AE, BE) with no additional arcs included in MST
- **b2A1:** CSO including all rejections correct and at the correct time (do not need to see AD, DE, DG, AB, BH rejected but if they are they must be rejected correctly (i.e. in this order) but note that AD, DE have the same weight as do DG and AB so they could appear in either order)
Note that stating all the arcs in order (e.g. FJ, EG, EF, EH, GH, BC, HJ, BD, FH, AE, BE, AD, DE, DG, AB, BH) and then stating only those in the tree in the correct order is fine for all three marks in this part
- **c1B1:** CAO (tree)
- **c2B1:** CAO (151)
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{b6d09c46-abfd-4baa-80bd-7485d1bf8e0d-03_759_1401_196_331}
\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 Kruskal's algorithm to find the minimum spanning tree for the network shown in Figure 1. You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in the minimum spanning tree.
\item Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2020 Q2 [8]}}