| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2020 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Kruskal's algorithm |
| Difficulty | Moderate -0.8 This is a standard textbook application of Kruskal's algorithm with a small network (7 vertices, ~12 edges). Part (a) is graph drawing from a table, part (b) requires sorting edges and systematically applying the algorithm (checking for cycles), and part (c) is simple addition. The algorithm is mechanical with no problem-solving insight required, making it easier than average A-level content. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | G | |
| A | - | 24 | - | 22 | 35 | - | - |
| B | 24 | - | 25 | 27 | - | - | - |
| C | - | 25 | - | 33 | 31 | 36 | 26 |
| D | 22 | 27 | 33 | - | - | 42 | - |
| E | 35 | - | 31 | - | - | 37 | 29 |
| F | - | - | 36 | 42 | 37 | - | 40 |
| G | - | - | 26 | - | 29 | 40 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct MST diagram with arcs: AB(27), BC(33), AD(22), CG, EG(42), CF shown | M1 | Either all arcs correct (ignore weights) or two arcs correct (including correct weights) |
| Fully correct diagram | A1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Kruskal's algorithm started: AD, AB, BC, CG, reject BD, EG, reject CE, reject CD, reject AE, CF, reject EF, reject FG, reject DF | M1 | First three arcs correctly chosen and at least one rejection seen at some point |
| All six arcs selected correctly: AD, AB, BC, CG, EG, CF only | A1 | CAO |
| All selections and rejections correct (in correct order and at correct time) | A1 | CSO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Weight of MST: 162 (km) | B1 | CAO (condone lack of units) |
# Question 1:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct MST diagram with arcs: AB(27), BC(33), AD(22), CG, EG(42), CF shown | M1 | Either all arcs correct (ignore weights) or two arcs correct (including correct weights) |
| Fully correct diagram | A1 | CAO |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Kruskal's algorithm started: AD, AB, BC, CG, reject BD, EG, reject CE, reject CD, reject AE, CF, reject EF, reject FG, reject DF | M1 | First three arcs correctly chosen and at least one rejection seen at some point |
| All six arcs selected correctly: AD, AB, BC, CG, EG, CF only | A1 | CAO |
| All selections and rejections correct (in correct order and at correct time) | A1 | CSO |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Weight of MST: 162 (km) | B1 | CAO (condone lack of units) |
---\begin{enumerate}
\item The table below shows the lengths, in km , of the roads in a network connecting seven towns, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$ and G .
\end{enumerate}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G \\
\hline
A & - & 24 & - & 22 & 35 & - & - \\
\hline
B & 24 & - & 25 & 27 & - & - & - \\
\hline
C & - & 25 & - & 33 & 31 & 36 & 26 \\
\hline
D & 22 & 27 & 33 & - & - & 42 & - \\
\hline
E & 35 & - & 31 & - & - & 37 & 29 \\
\hline
F & - & - & 36 & 42 & 37 & - & 40 \\
\hline
G & - & - & 26 & - & 29 & 40 & - \\
\hline
\end{tabular}
\end{center}
(a) By adding the arcs from vertex D along with their weights, complete the drawing of the network on Diagram 1 in the answer book.\\
(b) Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.\\
(c) State the weight of the minimum spanning tree.\\
\hfill \mbox{\textit{Edexcel FD1 2020 Q1 [6]}}