| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2022 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Calculate MST length/weight/cost |
| Difficulty | Easy -1.8 This is a straightforward application of Kruskal's or Prim's algorithm to find an MST from a small network diagram. It requires only mechanical execution of a standard algorithm with no problem-solving, proof, or novel insight—purely routine procedural work that is easier than typical A-level questions. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| e.g. \(A - B - F - H - J\) | B1 (1) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(A-B-C-D-E-G-F-H-J\) is not an example of a tour on T as although it contains every vertex it does not return to A | B1 (1) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Kruskal's: AC(9), BE(11), BF(12), not EF(14), FG(15), FH(17), not EG(18), EJ(20) | M1 | First four arcs (AC, BE, BF, FG) correctly chosen and at least one rejection seen |
| not HJ(21) or BC(21), not CE(23), not AB(24), CD(25) not DE, AD | A1 | All arcs selected correctly in correct order with no additional arcs |
| A1 | cso - all rejections correct and at correct time (DE and/or AD need not be rejected but if rejected must be after CD selected) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct MST diagram drawn (tree shown with vertices A–J) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 130 (km) | B1 | cao (130) – no units required/ignore units even if incorrect |
# Question 2:
## Part (a)
| Answer/Working | Marks | Guidance |
|---|---|---|
| e.g. $A - B - F - H - J$ | B1 **(1)** | |
## Part (b)
| Answer/Working | Marks | Guidance |
|---|---|---|
| $A-B-C-D-E-G-F-H-J$ is not an example of a tour on T as although it contains every vertex it does not return to A | B1 **(1)** | |
# Question 2(c):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Kruskal's: AC(9), BE(11), BF(12), not EF(14), FG(15), FH(17), not EG(18), EJ(20) | M1 | First four arcs (AC, BE, BF, FG) correctly chosen **and** at least one rejection seen |
| not HJ(21) or BC(21), not CE(23), not AB(24), CD(25) not DE, AD | A1 | All arcs selected correctly in correct order with no additional arcs |
| | A1 | cso - all rejections correct and at correct time (DE and/or AD need not be rejected but if rejected must be after CD selected) |
# Question 2(d):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct MST diagram drawn (tree shown with vertices A–J) | B1 | cao |
# Question 2(e):
| Answer | Marks | Guidance |
|--------|-------|----------|
| 130 (km) | B1 | cao (130) – no units required/ignore units even if incorrect |
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{765ea64e-d4b8-4f0f-9a43-2619f9db0c18-06_477_1052_239_504}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{765ea64e-d4b8-4f0f-9a43-2619f9db0c18-06_474_1052_1361_504}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
\section*{Question 2 continued}
\section*{D}
\begin{verbatim}
B
$$\mathrm { A }$$
\end{verbatim}
\begin{verbatim}
$\stackrel { \bullet } { \text { E } }$
\end{verbatim}
\section*{Diagram 1}
Weight of the minimum spanning tree: $\_\_\_\_$\\
\hfill \mbox{\textit{Edexcel D1 2022 Q2 [7]}}