| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Hamiltonian cycles |
| Difficulty | Moderate -0.5 This is a straightforward application of basic graph theory concepts from D1. Part (i) requires recognizing an Eulerian path (standard topic), part (ii) involves systematically checking for Hamiltonian cycles (routine enumeration on a small graph with 4 vertices), and part (iii) asks for a simple route finding. The graph is small enough that trial-and-error works, requiring minimal problem-solving insight beyond applying definitions. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles |
| Answer | Marks |
|---|---|
| (i) Ins and outs: One more out than in at D, vice versa at A. Start at D and end at A | M1; A1; B1 |
| (ii) Existence: \(ABDCA\); Uniqueness: Only alternative is \(ABC\ldots\); Extra arc: New possibility \(ADCB\ldots\) | B1; M1 A1; A1 |
| (iii) Route: \(BDCAB\) | B1 |
**(i)** Ins and outs: One more out than in at D, vice versa at A. Start at D and end at A | M1; A1; B1 |
**(ii)** Existence: $ABDCA$; Uniqueness: Only alternative is $ABC\ldots$; Extra arc: New possibility $ADCB\ldots$ | B1; M1 A1; A1 |
**(iii)** Route: $BDCAB$ | B1 |
---3 Fig. 3 shows a graph representing the seven bus journeys run each day between four rural towns. Each directed arc represents a single bus journey.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{ee39642f-f323-4614-a02a-4500199626de-4_317_515_392_772}
\captionsetup{labelformat=empty}
\caption{Fig. 3}
\end{center}
\end{figure}
(i) Show that if there is only one bus, which is in service at all times, then it must start at one town and end at a different town.
Give the start town and the end town.\\
(ii) Show that there is only one Hamilton cycle in the graph.
Show that, if an extra journey is added from your end town to your start town, then there is still only one Hamilton cycle.\\
(iii) A tourist is staying in town B. Give a route for her to visit every town by bus, visiting each town only once and returning to B .
Section B (48 marks)\\
\hfill \mbox{\textit{OCR MEI D1 2006 Q3 [8]}}