| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Game and interaction modeling |
| Difficulty | Moderate -0.8 This is a straightforward graph traversal exercise requiring basic tree diagram construction and path enumeration. All parts involve routine application of graph theory concepts with no novel problem-solving: drawing a simple tree, identifying a winning path, listing reachable nodes, and observing a cycle. The multi-part structure adds length but not conceptual difficulty. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges) |
**(i)** Produce the graph for the symbol 44. [1]
- M1: Correct graph with appropriate vertices and edges
**(ii)** Give two symbols each having the graph. [2]
- M1: First correct symbol identified
- M1: Second correct symbol identified
**(iii)** Produce the graph for the symbol 88. [2]
- M1: Correct identification of regions
- A1: Correct graph produced
**(iv)** Produce a single graph for the composite symbol 8888. [2]
- M1: Correct method for combining graphs
- A1: Correct composite graph
**(v)** Give the name of a connected graph with $n$ nodes and $n - 1$ arcs. [1]
- A1: Tree (or equivalent correct name)1 The bipartite graph in Fig. 1 represents a board game for two players. At each turn a player tosses a coin and moves their counter. The graph shows which square the counter is moved to if the coin shows heads, and which square if it shows tails. Each player starts with their counter on square 1. Play continues until one player gets their counter to square 9 and wins.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-002_723_1287_569_425}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
(i) Draw a tree to show all of the possibilities for the player's first three moves.\\
(ii) Show how a player can win in 3 turns.\\
(iii) List all squares which it is possible for a counter to occupy after 3 turns.\\
(iv) Show that a game can continue indefinitely.
\hfill \mbox{\textit{OCR MEI D1 Q1 [14]}}