| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2020 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Kruskal's algorithm |
| Difficulty | Easy -1.2 This is a straightforward application of Kruskal's algorithm with a small network (6 vertices, 10 edges). Students simply sort edges by weight and add them if they don't create a cycle—a mechanical procedure requiring only recall of the algorithm with no problem-solving or novel insight. The bookwork nature and routine execution make it easier than average. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| A | B | C | D | E | F | |
| A | - | 18 | 23 | 17 | 28 | 19 |
| B | 18 | - | 20 | 11 | - | 24 |
| C | 23 | 20 | - | - | 25 | 13 |
| D | 17 | 11 | - | - | - | 22 |
| E | 28 | - | 25 | - | - | - |
| F | 19 | 24 | 13 | 22 | - | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (a) Kruskal's algorithm: BD(11), CF(13), AD(17), reject AB(18), AF(19), reject BC(20), reject DF(22), reject AC(23), reject BF(24), CE(25) (not AE) | M1 A1 A1 (3) | a1M1: At least 8 correct arcs with corresponding correct values or all 11 correct arcs. a1A1: CSO (11 arcs only + correct values) – give bod. b1M1: Kruskal's: first three arcs (BD, CF, AD) correctly chosen and at least one rejection seen at some point. b1A1: All arcs in tree selected correctly and in the correct order (BD, CF, AD, AF, CE) – no other arcs in MST. b2A1: CSO including all rejections correct and at the correct time – AE need not be considered but if AE is considered then it must be rejected after CE has been added to the MST. |
| (b) Weight of MST = 85 (metres) | B1 (2) 7 marks | c1B1: CAO (tree). c2B1: CAO (85) |
| Answer | Marks | Guidance |
|--------|-------|----------|
| (a) Kruskal's algorithm: BD(11), CF(13), AD(17), reject AB(18), AF(19), reject BC(20), reject DF(22), reject AC(23), reject BF(24), CE(25) (not AE) | M1 A1 A1 (3) | a1M1: At least 8 correct arcs with corresponding correct values or all 11 correct arcs. a1A1: CSO (11 arcs only + correct values) – give bod. b1M1: Kruskal's: first three arcs (BD, CF, AD) correctly chosen and at least one rejection seen at some point. b1A1: All arcs in tree selected correctly and in the correct order (BD, CF, AD, AF, CE) – no other arcs in MST. b2A1: CSO including all rejections correct and at the correct time – AE need not be considered but if AE is considered then it must be rejected after CE has been added to the MST. |
| (b) Weight of MST = 85 (metres) | B1 (2) 7 marks | c1B1: CAO (tree). c2B1: CAO (85) |
---\begin{enumerate}
\item The table below shows the distances, in metres, between six vertices, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F , in a network.
\end{enumerate}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 18 & 23 & 17 & 28 & 19 \\
\hline
B & 18 & - & 20 & 11 & - & 24 \\
\hline
C & 23 & 20 & - & - & 25 & 13 \\
\hline
D & 17 & 11 & - & - & - & 22 \\
\hline
E & 28 & - & 25 & - & - & - \\
\hline
F & 19 & 24 & 13 & 22 & - & - \\
\hline
\end{tabular}
\end{center}
(a) Draw the weighted network using the vertices given in Diagram 1 in the answer book.\\
(b) Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the edges in the order that you consider them and state whether you are adding them to your minimum spanning tree.\\
(c) Draw the minimum spanning tree on Diagram 2 in the answer book and state its total weight.\\
\hfill \mbox{\textit{Edexcel D1 2020 Q1 [7]}}