| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Abstract shape and algorithm modeling |
| Difficulty | Moderate -0.8 This is a straightforward algorithmic trace question requiring careful following of instructions and pattern recognition. Students draw graphs for small cases (routine execution), then identify a simple linear pattern. No proof, minimal problem-solving, and the pattern emerges obviously from the examples. Easier than average A-level maths. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route |
| Answer | Marks | Guidance |
|---|---|---|
| (i)(a) Correct graph for (a) | B1 | |
| (i)(b) Correct graph for (b) | B1 | |
| (i)(c) Clearly correct graph for (c) | B1 | |
| (i)(d) Clearly correct graph for (d) | B1 | |
| (ii) \(2n\) if \(n\) is even; \(2n + 1\) if \(n\) is odd | (4) M1 (2) A1 | For treating the cases \(n\) odd and \(n\) even separately; For both rules correct |
| \(\mathbf{6}\) |
**(i)(a)** Correct graph for (a) | B1 |
**(i)(b)** Correct graph for (b) | B1 |
**(i)(c)** Clearly correct graph for (c) | B1 |
**(i)(d)** Clearly correct graph for (d) | B1 |
**(ii)** $2n$ if $n$ is even; $2n + 1$ if $n$ is odd | (4) M1 (2) A1 | For treating the cases $n$ odd and $n$ even separately; For both rules correct |
| | $\mathbf{6}$ |3 Consider the following algorithm.\\
Step 1: Input a positive integer $n$.\\
Step 2 : Draw a graph consisting of $n$ vertices and no arcs.\\
Step 3 : Create a new vertex and join it directly to every vertex of order 0.\\
Step 4: Create a new vertex and join it directly to every vertex of odd order.\\
Step 5 : Stop.\\
(i) Draw separate diagrams to show the result of applying this algorithm in the following cases.
\begin{enumerate}[label=(\alph*)]
\item $n = 1$
\item $n = 2$
\item $n = 3$
\item $n = 4$\\
(ii) State how many arcs are in the graph that results when the algorithm is applied to a set of $n$ vertices.
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2006 Q3 [6]}}