| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Minimum Spanning Trees |
| Type | Define tree terminology |
| Difficulty | Easy -1.8 This question tests basic graph theory definitions (order of nodes, minimum connector) with minimal calculation. Parts (i-ii) require simple counting, (iii) is a practical reasoning question, and (iv) tests conceptual understanding of MST vs minimum connections. All parts are straightforward recall and application of elementary Decision Maths concepts with no complex problem-solving required. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms |
| Answer | Marks |
|---|---|
| (i) Any connected tree. | M1 A1 |
| 12 connections | B1 |
| (ii) 14 connections | B1 |
| (iii) e.g. He might be able to save cable by using it. e.g. To avoid overloading. | B1 |
| (iv) Yes. A minimum connector is a tree. This gives the min number of arcs \((n-1)\). This gives the minimum no of connections \((2(n-1))\). | B1 B1 B1 |
| (i) Any connected tree. | M1 A1 | |
| 12 connections | B1 | |
| (ii) 14 connections | B1 | |
| (iii) e.g. He might be able to save cable by using it. e.g. To avoid overloading. | B1 | |
| (iv) Yes. A minimum connector is a tree. This gives the min number of arcs $(n-1)$. This gives the minimum no of connections $(2(n-1))$. | B1 B1 B1 | |1 Answer this question on the insert provided.
The nodes in the unfinished graph in Fig. 1 represent six components, A, B, C, D, E, F and the mains. The components are to be joined by electrical cables to the mains. Each component can be joined directly to the mains, or can be joined via other components.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-2_486_879_623_607}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
The total number of connections that the electrician has to make is the sum of the orders of the nodes in the finished graph.\\
(i) Draw arcs representing suitable cables so that the electrician has to make as few connections as possible. Give this number.
The electrician has a junction box. This can be represented by an eighth node on the graph.\\
(ii) What is the minimum number of connections which the electrician will have to make if he uses the junction box?\\
(iii) The electrician has to make more connections if he uses his junction box. Why might he choose to use it anyway?
The electrician decides not to use the junction box. He measures each of the distances between pairs of nodes, and records them in a complete graph. He then constructs a minimum connector for his graph to find which nodes to connect.\\
(iv) Will this result in the minimum number of connections? Justify your answer.
\hfill \mbox{\textit{OCR MEI D1 2005 Q1 [8]}}