| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Compare Prim's and Kruskal's algorithms |
| Difficulty | Moderate -0.8 This is a straightforward application of standard D1 algorithms requiring only procedural execution of Prim's algorithm (selecting edges in order) and recall of differences between two algorithms. No problem-solving, proof, or novel insight required—purely algorithmic recall and comparison, making it easier than average A-level maths questions. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | |
| A | - | 85 | 110 | 160 | 225 | 195 |
| B | 85 | - | 100 | 135 | 180 | 150 |
| C | 110 | 100 | - | 215 | 200 | 165 |
| D | 160 | 135 | 215 | - | 235 | 215 |
| E | 225 | 180 | 200 | 235 | - | 140 |
| F | 195 | 150 | 165 | 215 | 140 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Starting at | Minimum arcs required for M1 | Nodes |
| A | AB BC BD | ABCD(FE) |
| B | AB BC BD | BACD(FE) |
| C | BC AB BD | CBAD(FE) |
| D | BD AB BC | DBAC(FE) |
| E | EF BF AB | EFBA(CD) |
| F | EF BF AB | FEBA(CD) |
**Question 2 Notes:**
- a1M1: Prim's – first three arcs correctly chosen or first four nodes correctly chosen, in order. Any rejections seen during selection is M0. Order of nodes may be seen across the top of the matrix {1, 2, 3, 4, -, -}
- a1A1: First four arcs correctly chosen or all six nodes correctly chosen {A, B, C, D, F, E}. Order of nodes may be seen across the top of the matrix {1, 2, 3, 4, 5, 6}
- a2A1: CSO (must be considering arcs for this final mark)
**Misread:** Starting at a node other than A scores M1 only – must have the first three arcs (or four nodes or numbers) correct.
| Starting at | Minimum arcs required for M1 | Nodes | order |
|---|---|---|---|
| A | AB BC BD | ABCD(FE) | 1234(65) |
| B | AB BC BD | BACD(FE) | 2134(65) |
| C | BC AB BD | CBAD(FE) | 3214(65) |
| D | BD AB BC | DBAC(FE) | 3241(65) |
| E | EF BF AB | EFBA(CD) | 43(56)12 |
| F | EF BF AB | FEBA(CD) | 43(56)21 |
- b1B1: CAO (weights on arcs not required)
- c1B1: CAO (condone lack of/incorrect units)
- d1B1: One correct statement
- d2B1: A second correct statement
- d3B1: A third correct statement
In part (d) all technical language must be correct (so do not condone point for vertex/node etc.)2.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 85 & 110 & 160 & 225 & 195 \\
\hline
B & 85 & - & 100 & 135 & 180 & 150 \\
\hline
C & 110 & 100 & - & 215 & 200 & 165 \\
\hline
D & 160 & 135 & 215 & - & 235 & 215 \\
\hline
E & 225 & 180 & 200 & 235 & - & 140 \\
\hline
F & 195 & 150 & 165 & 215 & 140 & - \\
\hline
\end{tabular}
\end{center}
The table shows the average journey time, in minutes, between six towns, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F .
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network. You must list the arcs that form your tree in the order in which you selected them.
\item Draw your tree using the vertices given in Diagram 1 in the answer book.
\item Find the weight of your minimum spanning tree.
Kruskal's algorithm may also be used to find a minimum spanning tree.
\item State three differences between Prim's algorithm and Kruskal's algorithm.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q2 [8]}}