| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Apply Kruskal's algorithm |
| Difficulty | Moderate -0.3 This is a standard D1 minimum spanning tree question requiring routine application of Kruskal's and Prim's algorithms with clear step-by-step procedures. Part (iii) requires some interpretation but the reasoning is straightforward (likely symmetry/balance and avoiding shared edges). While it has multiple parts and requires careful bookkeeping, it involves no novel problem-solving or deep insight—just methodical execution of well-practiced algorithms. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| A | B | C | D | E | F | |
| A | \(-\) | 7 | \(-\) | \(-\) | 12 | \(-\) |
| B | 7 | \(-\) | 5 | 3 | 6 | 6 |
| C | \(-\) | 5 | \(-\) | 8 | 4 | 7 |
| D | \(-\) | 3 | 8 | \(-\) | 1 | 5 |
| E | 12 | 6 | 4 | 1 | \(-\) | 7 |
| F | \(-\) | 6 | 7 | 5 | 7 | \(-\) |
In a factory a network of pipes connects 6 vats, A, B, C, D, E and F. Two separate connectors need to be chosen from the network The table shows the lengths of pipes (metres) connecting the 6 vats.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
& A & B & C & D & E & F \\
\hline
A & $-$ & 7 & $-$ & $-$ & 12 & $-$ \\
\hline
B & 7 & $-$ & 5 & 3 & 6 & 6 \\
\hline
C & $-$ & 5 & $-$ & 8 & 4 & 7 \\
\hline
D & $-$ & 3 & 8 & $-$ & 1 & 5 \\
\hline
E & 12 & 6 & 4 & 1 & $-$ & 7 \\
\hline
F & $-$ & 6 & 7 & 5 & 7 & $-$ \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\item Use Kruskal's algorithm to find a minimum connector. Show the order in which you select pipes, draw your connector and give its total length. [5]
\item Produce a new table excluding the pipes which you selected in part (i). Use the tabular form of Prim's algorithm to find a second minimum connector from this reduced set of pipes. Show your working, draw your connector and give its total length. [7]
\item The factory manager prefers the following pair of connectors:
$\{$AB, BC, BD, BE, BF$\}$ and $\{$AE, BF, CE, DE, DF$\}$.
Give two possible reasons for this preference. [4]
\end{enumerate}
\hfill \mbox{\textit{OCR MEI D1 2007 Q6 [16]}}