| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Prim's algorithm from vertex |
| Difficulty | Easy -1.3 This is a straightforward application of Prim's algorithm to a small 6-vertex network given in table form, followed by routine application of Kruskal's algorithm. The question requires only mechanical execution of standard algorithms with no problem-solving insight or novel reasoning—purely procedural recall of D1 content that is significantly easier than typical pure maths questions. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | |
| A | - | 15 | 6 | 9 | - | - |
| B | 15 | - | 12 | - | 14 | - |
| C | 6 | 12 | - | 7 | 10 | - |
| D | 9 | - | 7 | - | 11 | 17 |
| E | - | 14 | 10 | 11 | - | 5 |
| F | - | - | - | 17 | 5 | - |
| Answer | Marks |
|---|---|
| AC, CD, CE; EF; BC | M1; A1; A1 (3) |
| B1 (1) | |
| B1 B1 (2) | |
| EF, AC, CD, reject AD, CE, reject DE, CB | M1 A1 A1 (3) |
| Time = 40 (days) | B1 (1) |
| 10 marks |
| Answer | Marks | Guidance |
|---|---|---|
| Starting at | Minimum arcs required for M1 | Nodes |
| A | AC CD CE | ACDE(FB) |
| B | BC AC CD | BCAD(EF) |
| C | AC CD CE | CADE(FB) |
| D | CD AC CE | DCAE(FB) |
| E | EF CE AC | EFCA(DB) |
| F | EF CE AC | FECA(DB) |
| AC, CD, CE; EF; BC | M1; A1; A1 (3) | |
| | B1 (1) | |
| | B1 B1 (2) | |
| EF, AC, CD, reject AD, CE, reject DE, CB | M1 A1 A1 (3) | |
| Time = 40 (days) | B1 (1) |
| | | 10 marks |
**Notes for Question 3:**
Accept the weight of each arc to represent the arcs (as each value is unique).
- a1M1: Prim's – first three arcs correctly chosen or first four nodes correctly chosen {A, C, D, E, ...}. Any rejections seen during selection M0. Order of nodes may be seen at the top of the matrix {1, –, 2, 3, 4, –}
- a1A1: First four arcs correctly chosen or all six nodes correctly chosen {A, C, D, E, F, B}. Order of nodes may be seen at the top of the matrix {1, 6, 2, 3, 4, 5}
- 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 | AC CD CE | ACDE(FB) | 1(6)234(5) |
| B | BC AC CD | BCAD(EF) | 3124(56) |
| C | AC CD CE | CADE(FB) | 2(6)134(5) |
| D | CD AC CE | DCAE(FB) | 3(6)214(5) |
| E | EF CE AC | EFCA(DB) | 4(6)3(5)12 |
| F | EF CE AC | FECA(DB) | 4(6)3(5)21 |
- b1B1: CAO (weights not required)
- c1B1: Any four arcs added correctly (weights not required)
- c2B1: CAO (including weights) – bod if arcs 'appear' to be crossed out (they may be using the network diagram to answer part (d)).
- d1M1: Kruskal's – first three arcs correctly chosen and **at least one rejection seen at some point**.
- d1A1: All five arcs selected correctly EF, AC, CD, CE, CB.
- d2A1: CAO All selections and rejections correct (in correct order and at the correct time).
**Listing all the arcs in order and then listing those arcs in the tree in the correct order is fine for full marks** (this implies that rejections are correct and at the correct time)
**Listing all the arcs in order and just drawing the MST is M0**
**SC for part (d):** If the network diagram is incorrect in part (c) and it is clear that the candidate has used part (c) (instead of the original table) to answer part (d) then award M1 only for the first three arcs correctly chosen and at least one rejection seen at some point provided their network is connected and contains at least nine arcs.
- e1B1: CAO (ignore lack/incorrect units)
---3.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
& A & B & C & D & E & F \\
\hline
A & - & 15 & 6 & 9 & - & - \\
\hline
B & 15 & - & 12 & - & 14 & - \\
\hline
C & 6 & 12 & - & 7 & 10 & - \\
\hline
D & 9 & - & 7 & - & 11 & 17 \\
\hline
E & - & 14 & 10 & 11 & - & 5 \\
\hline
F & - & - & - & 17 & 5 & - \\
\hline
\end{tabular}
\end{center}
The table shows the times, in days, needed to repair the network of roads between six towns, A, B, C, D, E and F, following a flood.
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm, starting at A , to find the minimum connector for this network. You must list the arcs that form your tree in the order that you selected them.
\item Draw your minimum connector using the vertices given in Diagram 1 in the answer book.
\item Add arcs from D, E and F to Diagram 2 in the answer book, so that it shows the network of roads shown by the table.
\item Use Kruskal's algorithm to find the minimum connector. 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 connector.
\item State the minimum time needed, in days, to reconnect the six towns.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q3 [10]}}