| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Eulerian classification |
| Difficulty | Moderate -0.8 This is a straightforward D1 question testing basic graph theory definitions and Eulerian path concepts. Parts (i)-(iv) require simple recall and observation (identifying cycles, paths, spanning tree properties, checking vertex degrees). Part (v) applies the standard 'odd vertices รท 2' formula. Part (vi) requires minimal reasoning about pairing odd vertices. All parts are routine textbook exercises with no novel problem-solving required. |
| 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, route7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| (i) | Example: \(N - P - Q - T - S - R - N\) or \(P - Q - S - P\) | B1 |
| (ii) | It passes through P twice | B1 |
| (iii) | Neither | B1 |
| (iv) | \(A\): neither \(B\): semi-Eulerian | B1 |
| (v) | \(A\): 2 \(B\): 1 | B1, 2 |
| (vi) | There are 4 odd nodes \((N, P, S \text{ and } Z)\) To connect these we must add 2 arcs | M1, A1, 9 |
(i) | Example: $N - P - Q - T - S - R - N$ or $P - Q - S - P$ | B1 | Any valid cycle (closed and does not repeat vertices, need not be a Hamiltonian cycle)
(ii) | It passes through P twice | B1 | Or, it includes a cycle (accept "loop")
(iii) | Neither | B1 | If graphs are not specified, assume $A$ is first
(iv) | $A$: neither $B$: semi-Eulerian | B1 | If graphs are not specified, assume $A$ is first
(v) | $A$: 2 $B$: 1 | B1, 2 |
(vi) | There are 4 odd nodes $(N, P, S \text{ and } Z)$ To connect these we must add 2 arcs | M1, A1, 9 | For 2 Seen or implied
---1 Two graphs A and B are shown below.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{dbf782dd-879c-4f0f-b532-246a0db9f130-2_339_585_333_386}
\captionsetup{labelformat=empty}
\caption{Graph $A$}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{dbf782dd-879c-4f0f-b532-246a0db9f130-2_337_579_333_1174}
\captionsetup{labelformat=empty}
\caption{Graph B}
\end{center}
\end{figure}
(i) Write down an example of a cycle on graph A .\\
(ii) W hy is $\mathrm { U } - \mathrm { Y } - \mathrm { V } - \mathrm { Z } - \mathrm { Y } - \mathrm { X }$ not a path on graph B ?\\
(iii) How many arcs would there be in a spanning tree for graph A ?\\
(iv) For each graph state whether it is Eulerian, semi-Eulerian or neither.\\
(v) The graphs show designs to be etched on metal plates. The etching tool is positioned at a starting point and follows a route without repeating any arcs. It may be lifted off and positioned at a new starting point. W hat is the smallest number of times that the etching tool must be positioned, including the initial position, to draw each graph?
An arc is drawn connecting Q to U , so that the two graphs become one. The resulting graph is not Eulerian.\\
(vi) Extra arcs are then added to make an Eulerian graph. W hat is the smallest number of extra arcs that need to be added?
\hfill \mbox{\textit{OCR D1 2007 Q1 [9]}}