| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Kruskal's algorithm |
| Difficulty | Easy -1.3 This is a straightforward application of Kruskal's algorithm to a small 6-vertex network with clearly tabulated edge weights. The algorithm is mechanical (sort edges, add if no cycle), requires no problem-solving insight, and is a standard textbook exercise testing only procedural recall of the algorithm. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method |
| \(\mathbf { A }\) | \(\mathbf { B }\) | \(\mathbf { C }\) | \(\mathbf { D }\) | \(\mathbf { E }\) | \(\mathbf { F }\) | |
| \(\mathbf { A }\) | - | 24 | - | - | 23 | 22 |
| \(\mathbf { B }\) | 24 | - | 18 | 19 | 17 | 20 |
| \(\mathbf { C }\) | - | 18 | - | 11 | 14 | - |
| \(\mathbf { D }\) | - | 19 | 11 | - | 13 | - |
| \(\mathbf { E }\) | 23 | 17 | 14 | 13 | - | 21 |
| \(\mathbf { F }\) | 22 | 20 | - | - | 21 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Network drawn with correct structure | M1 | More than 10 arcs |
| All arcs correct | A1 | All arcs correct |
| All values correct (AF=22, AB=24, AE=23, BF=20, BE=17, BF=19, CE=18, CF=14, CD=11, DE=13, DF=21) | A1 | All values correct |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| CD, DE, reject CE, BE, reject BC, reject BD, BF, reject EF, AF | M1 A1 | First three arcs correctly chosen; All used arcs selected correctly |
| 11, 13, 14, 17, 18, 19, 20, 21, 22 | A1 | All rejected arcs selected in correct order |
| Minimum spanning tree diagram showing CD, DE, BE, BF, AF | B1 | CAO for arcs – numbers not needed. NO ft |
| Weight of tree \(= 83\) (m) | B1 | CAO 83, condone units |
# Question 2:
## Part (a)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Network drawn with correct structure | M1 | More than 10 arcs |
| All arcs correct | A1 | All arcs correct |
| All values correct (AF=22, AB=24, AE=23, BF=20, BE=17, BF=19, CE=18, CF=14, CD=11, DE=13, DF=21) | A1 | All values correct |
## Part (b)
| Answer/Working | Marks | Guidance |
|---|---|---|
| CD, DE, reject CE, BE, reject BC, reject BD, BF, reject EF, AF | M1 A1 | First three arcs correctly chosen; All used arcs selected correctly |
| 11, 13, 14, 17, 18, 19, 20, 21, 22 | A1 | All rejected arcs selected in correct order |
| Minimum spanning tree diagram showing CD, DE, BE, BF, AF | B1 | CAO for arcs – numbers not needed. NO ft |
| Weight of tree $= 83$ (m) | B1 | CAO 83, condone units |
---2.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
& $\mathbf { A }$ & $\mathbf { B }$ & $\mathbf { C }$ & $\mathbf { D }$ & $\mathbf { E }$ & $\mathbf { F }$ \\
\hline
$\mathbf { A }$ & - & 24 & - & - & 23 & 22 \\
\hline
$\mathbf { B }$ & 24 & - & 18 & 19 & 17 & 20 \\
\hline
$\mathbf { C }$ & - & 18 & - & 11 & 14 & - \\
\hline
$\mathbf { D }$ & - & 19 & 11 & - & 13 & - \\
\hline
$\mathbf { E }$ & 23 & 17 & 14 & 13 & - & 21 \\
\hline
$\mathbf { F }$ & 22 & 20 & - & - & 21 & - \\
\hline
\end{tabular}
\end{center}
The table shows the distances, in metres, between six vertices, $\mathbf { A } , \mathbf { B } , \mathbf { C } , \mathbf { D } , \mathbf { E }$ and $\mathbf { F }$, in a network.
\begin{enumerate}[label=(\alph*)]
\item Draw the weighted network using the vertices given in Diagram 1 in the answer booklet.
\item Use Kruskal's algorithm to find a minimum spanning tree. You should list the edges in the order that you consider them and state whether you are adding them to your minimum spanning tree.
\item Draw your tree on Diagram 2 in the answer booklet and find its total weight.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2009 Q2 [8]}}