| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Physical space modeling |
| Difficulty | Easy -1.3 This is a straightforward D1 graph theory question testing basic definitions and concepts. Parts (i)-(iv) require simple identification of regions and their adjacencies with minimal problem-solving, while part (v) is direct recall of the definition of a tree. The entire question is routine application of fundamental graph concepts with no novel insight required. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected |
Each of the following symbols consists of boundaries enclosing regions.
\includegraphics{figure_1}
The symbol representing zero has three regions, the outside, that between the two boundaries and the inside.
To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for
\includegraphics{figure_2}
is $\bullet \longrightarrow \bullet \longrightarrow \bullet$.
\begin{enumerate}[label=(\roman*)]
\item Produce the graph for the symbol \includegraphics{figure_3}. [1]
\item Give two symbols each having the graph $\bullet \longrightarrow \bullet$. [2]
\item Produce the graph for the symbol \includegraphics{figure_4}. [2]
\item Produce a single graph for the composite symbol \includegraphics{figure_5}. [2]
\item Give the name of a connected graph with $n$ nodes and $n - 1$ arcs. [1]
\end{enumerate}
\hfill \mbox{\textit{OCR MEI D1 2007 Q1 [8]}}