| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 5 |
| 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 graph theory question requiring students to draw a simple 3×3 grid graph (which has a standard structure), count shortest path length by inspection, and apply the basic Eulerian path theorem by checking vertex degrees. All steps are routine applications of D1 definitions with no problem-solving insight required. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02c Graph terminology: walk, trail, path, cycle, route7.02g Eulerian graphs: vertex degrees and traversability |
A puzzle involves a 3 by 3 grid of squares, numbered 1 to 9, as shown in Fig. 1a below. Eight of the squares are covered by blank tiles. Fig. 1b shows the puzzle with all of the squares covered except for square 4. This arrangement of tiles will be called position 4.
\includegraphics{figure_1}
A move consists of sliding a tile into the empty space. From position 4, the next move will result in position 1, position 5 or position 7.
\begin{enumerate}[label=(\roman*)]
\item Draw a graph with nine vertices to represent the nine positions and arcs that show which positions can be reached from one another in one move. What is the least number of moves needed to get from position 1 to position 9? [3]
\item State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is. [2]
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2008 Q2 [5]}}