| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Network and route modeling |
| Difficulty | Moderate -0.8 This is a straightforward enumeration exercise in basic graph theory requiring systematic listing of paths and routes. While it requires careful organization to avoid missing cases, it involves only direct application of definitions with no problem-solving insight or complex reasoning—making it easier than a typical A-level question. |
| 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, route |
| Answer | Marks |
|---|---|
| \(T_1 \to T_2\), \(T_1 \to T_3\), \(T_1 \to T_3\), \(T_1 \to T_2 \to T_3\), \(T_1 \to T_2 \to T_3 \to T_4\), \(T_1 \to T_3 \to T_4\) | M1 A1 |
| Answer | Marks |
|---|---|
| \(T_4 \to T_3 \to T_2 \to T_1\), \(T_4 \to T_3 \to T_1\), \(T_4 \to T_3 \to T_1 \to T_2\), \(T_4 \to T_3\), \(T_4 \to T_3\) | M1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| 22 | M1 A1 M1 | allow for 23; halving (not 11.5) |
| Answer | Marks | Guidance |
|---|---|---|
| 11 | M1 A1 | halving (not 11.5) |
**(i)**
| $T_1 \to T_2$, $T_1 \to T_3$, $T_1 \to T_3$, $T_1 \to T_2 \to T_3$, $T_1 \to T_2 \to T_3 \to T_4$, $T_1 \to T_3 \to T_4$ | M1 A1 | |
**(ii)**
| $T_4 \to T_3 \to T_2 \to T_1$, $T_4 \to T_3 \to T_1$, $T_4 \to T_3 \to T_1 \to T_2$, $T_4 \to T_3$, $T_4 \to T_3$ | M1 A1 | |
**(iii)**
| 22 | M1 A1 M1 | allow for 23; halving (not 11.5) |
**(iv)**
| 11 | M1 A1 | halving (not 11.5) |3 The graph represents four towns together with (two-way) roads connecting them.\\
\includegraphics[max width=\textwidth, alt={}, center]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-4_191_286_319_886}
A path is a set of connected arcs linking one vertex to another. A path contains no repeated vertex. $\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }$ and $\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }$ are paths.\\
(i) There are six paths from $\mathrm { T } _ { 1 }$. List them.\\
(ii) List the paths from $\mathrm { T } _ { 4 }$.\\
(iii) How many paths are there altogether?
For this question a route is defined to be a path in which the direction of the arcs is not relevant. Thus $\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }$ and $\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 1 }$ are the same route. Similarly $\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }$ and $\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 1 }$ are the same route (but note that $\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 } \rightarrow \mathrm {~T} _ { 3 }$ is different).\\
(iv) How many routes are there altogether?
\hfill \mbox{\textit{OCR MEI D1 2008 Q3 [8]}}