| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 5 |
| 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 from a given starting vertex with a complete distance table. The algorithm is purely procedural with no problem-solving required—students simply follow the standard steps of selecting minimum edges. With only 6 vertices, the computation is manageable and routine for D1 students who have practiced the algorithm. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| \(\mathbf { A }\) | \(\mathbf { B }\) | \(\mathbf { C }\) | \(\mathbf { D }\) | \(\mathbf { E }\) | \(\mathbf { F }\) | |
| \(\mathbf { A }\) | - | 135 | 180 | 70 | 95 | 225 |
| \(\mathbf { B }\) | 135 | - | 215 | 125 | 205 | 240 |
| \(\mathbf { C }\) | 180 | 215 | - | 150 | 165 | 155 |
| \(\mathbf { D }\) | 70 | 125 | 150 | - | 100 | 195 |
| \(\mathbf { E }\) | 95 | 205 | 165 | 100 | - | 215 |
| \(\mathbf { F }\) | 225 | 240 | 155 | 195 | 215 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: AD, AE, DB; DC, CF | M1 A1; A1 | (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: (diagram showing network) | B1 | (1) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Weight 595 (km) | B1 | (1) |
**Part (a)**
Answer: AD, AE, DB; DC, CF | M1 A1; A1 | (3) | Using Prim – first 2 arcs probably but condone starting from another vertex. 1A1: first three arcs correct. 2A1: all correct. Apply the misread rule, if not listing arcs or not starting at A. So for M1 only. Accept numbers across the top (condoning absence of 6). Accept full vertex listing. Accept full arc listing starting from vertex other than A.
**Part (b)**
Answer: (diagram showing network) | B1 | (1) | CAO
**Part (c)**
Answer: Weight 595 (km) | B1 | (1) | CAO condone lack of km. [AD AE DB DC CF] {1 4 5 2 3 6} ADEBCF; BD AD AE CD CF {3 1 5 2 4 6} BDAECF; CD AD AE BD CF {3 5 1 2 4 6} CDAEBF; DA AE DB CD CF {2 4 5 1 3 6} DAEBCF; EA AD DB DC CF {2 4 5 3 1 6} EADBCF; FC CD AD AE BD {4 6 2 3 5 1} FCDAEB
---1.
\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 }$ & - & 135 & 180 & 70 & 95 & 225 \\
\hline
$\mathbf { B }$ & 135 & - & 215 & 125 & 205 & 240 \\
\hline
$\mathbf { C }$ & 180 & 215 & - & 150 & 165 & 155 \\
\hline
$\mathbf { D }$ & 70 & 125 & 150 & - & 100 & 195 \\
\hline
$\mathbf { E }$ & 95 & 205 & 165 & 100 & - & 215 \\
\hline
$\mathbf { F }$ & 225 & 240 & 155 & 195 & 215 & - \\
\hline
\end{tabular}
\end{center}
The table shows the lengths, in km, of potential rail routes 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 from A , to find a minimum spanning tree for this table. You must list the arcs that form your tree in the order that they are selected.
\item Draw your tree using the vertices given in Diagram 1 in the answer book.
\item State the total weight of your tree.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2009 Q1 [5]}}