| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Kruskal's algorithm |
| Difficulty | Moderate -0.8 This is a straightforward application of Kruskal's algorithm with a small network (7 vertices). The procedure is algorithmic and routine: list edges in ascending order, add if no cycle forms. Requires careful bookkeeping but no problem-solving insight or novel thinking—purely procedural execution of a standard D1 algorithm. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | G | |
| A | - | 15 | 19 | - | 22 | 24 | - |
| B | 15 | - | - | 8 | 13 | - | - |
| C | 19 | - | - | 12 | - | 16 | - |
| D | - | 8 | 12 | - | 10 | - | 18 |
| E | 22 | 13 | - | 10 | - | 15 | 16 |
| F | 24 | - | 16 | - | 15 | - | 17 |
| G | - | - | - | 18 | 16 | 17 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| All four arcs correct: B–D(8), D–E(10), D–C(12), D–G(18) shown in diagram | 1B1 | All four arcs CAO; if three arcs and weights correct give B1 B0 |
| All four weights correct | 2B1 (2) | If extra arcs and weights, remove second B mark |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| BD(8), DE(10), CD(12), reject BE(13), then \(\{\)EF(15), AB(15)\(\}\), \(\{\)EG(16), reject CF(16)\(\}\), reject remainder | M1, 1A1, 2A1 (3) | First three arcs correctly chosen and at least one rejection seen (Kruskal not Prim); first five arcs: BD, DE, CD, then EF, AB |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Correct spanning tree diagram shown (A, B, D, C, E, F, G all connected) | B1 (1) | CAO, condone missing weights |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Weight of tree \(= 76\) (km) | B1 (1) | CAO |
## Question 3:
### Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| All four arcs correct: B–D(8), D–E(10), D–C(12), D–G(18) shown in diagram | 1B1 | All four arcs CAO; if three arcs and weights correct give B1 B0 |
| All four weights correct | 2B1 **(2)** | If extra arcs and weights, remove second B mark |
### Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| BD(8), DE(10), CD(12), reject BE(13), then $\{$EF(15), AB(15)$\}$, $\{$EG(16), reject CF(16)$\}$, reject remainder | M1, 1A1, 2A1 **(3)** | First three arcs correctly chosen and at least one rejection seen (Kruskal not Prim); first five arcs: BD, DE, CD, then EF, AB |
### Part (c):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Correct spanning tree diagram shown (A, B, D, C, E, F, G all connected) | B1 **(1)** | CAO, condone missing weights |
### Part (d):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Weight of tree $= 76$ (km) | B1 **(1)** | CAO |
---3.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | }
\hline
& A & B & C & D & E & F & G \\
\hline
A & - & 15 & 19 & - & 22 & 24 & - \\
\hline
B & 15 & - & - & 8 & 13 & - & - \\
\hline
C & 19 & - & - & 12 & - & 16 & - \\
\hline
D & - & 8 & 12 & - & 10 & - & 18 \\
\hline
E & 22 & 13 & - & 10 & - & 15 & 16 \\
\hline
F & 24 & - & 16 & - & 15 & - & 17 \\
\hline
G & - & - & - & 18 & 16 & 17 & - \\
\hline
\end{tabular}
\end{center}
The table shows the lengths, in km, of a network of roads between seven villages, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$ and G.
\begin{enumerate}[label=(\alph*)]
\item Complete the drawing of the network in Diagram 1 of the answer book by adding the necessary arcs from vertex D together with their weights.
\item 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.
\item Draw the minimum spanning tree using the vertices provided in Diagram 2 in the answer book.
\item State the weight of the minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2012 Q3 [7]}}