| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | Specimen |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Kruskal's algorithm |
| Difficulty | Easy -1.2 This is a standard textbook application of Kruskal's algorithm to a small network with clearly labeled edges. It requires only systematic execution of a memorized algorithm with no problem-solving insight, making it significantly easier than average A-level questions which typically require some conceptual understanding or multi-step reasoning. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| DE GF DC \(\left\{\begin{array}{l}\text{not CE}\\ \text{BD}\end{array}\right\}\) EG (not EF not CF) AC (not AB) GH | M1 A1, A1 | 3 marks total; 1M1: Kruskal's algorithm – first 4 arcs selected correctly; 1A1: All seven non-rejected arcs chosen correctly; 2A1: All rejections correct and in correct order and at correct time |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Distance matrix completed correctly | B2, 1, 0 | 2 marks total; condone two (double) errors; 2B1: cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| AC CD DE BD GE GF GH | M1 A1, A1 | 3 marks total; 1M1: Prim's algorithm – first four arcs chosen correctly in order, or first five nodes chosen correctly in order \(\{A,C,D,E,B\ldots\}\); 1A1: First six arcs correct or all 8 nodes correct in order \(\{A,C,D,E,B,G,F,H\}\); 2A1: All correct and arcs chosen in correct order |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Weight: 174 | B1 | 1 mark; cao |
# Question 2:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| DE GF DC $\left\{\begin{array}{l}\text{not CE}\\ \text{BD}\end{array}\right\}$ EG (not EF not CF) AC (not AB) GH | M1 A1, A1 | **3 marks total**; 1M1: Kruskal's algorithm – first 4 arcs selected correctly; 1A1: All seven non-rejected arcs chosen correctly; 2A1: All rejections correct and in correct order and at correct time |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Distance matrix completed correctly | B2, 1, 0 | **2 marks total**; condone two (double) errors; 2B1: cao |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| AC CD DE BD GE GF GH | M1 A1, A1 | **3 marks total**; 1M1: Prim's algorithm – first four arcs chosen correctly in order, **or** first five nodes chosen correctly in order $\{A,C,D,E,B\ldots\}$; 1A1: First six arcs correct **or** all 8 nodes correct in order $\{A,C,D,E,B,G,F,H\}$; 2A1: All correct and arcs chosen in correct order |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Weight: 174 | B1 | **1 mark**; cao |
**Total: 9 marks**
---2.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5fa867a2-0a3d-4f0b-9f9c-15584f2be5c0-03_719_1161_223_452}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 represents the distances, in metres, between eight vertices, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }$ and H , in a network.
\begin{enumerate}[label=(\alph*)]
\item Use Kruskal's algorithm to find a minimum spanning tree for the network.
You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
\item Complete Matrix 1 in your answer book, to represent the network.
\item Starting at A, use Prim's algorithm to determine a minimum spanning tree. You must clearly state the order in which you considered the vertices and the order in which you included the arcs.
\item State the weight of the minimum spanning tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q2 [9]}}