| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Physical space modeling |
| Difficulty | Moderate -0.8 This is a straightforward graph theory application question requiring basic vertex-edge counting and simple graph drawing. Part (i) is direct translation to a graph, parts (ii-iii) involve elementary arithmetic (counting edges in a star graph), and part (iv) reverses the process. No complex algorithms, proofs, or novel problem-solving required—purely mechanical application of basic D1 concepts. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02r Graph modelling: model and solve problems using graphs |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Example: a tree (shown with dots and edges) | M1 A1 B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 13 | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 14 | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Example diagrams showing x marks arranged vertically with circled symbol | M1 A1 A1 |
**Part (i)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Example: a tree (shown with dots and edges) | M1 A1 B1 | |
**Part (ii)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| 13 | B1 | |
**Part (iii)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| 14 | B1 | |
**Part (iv)**
| Answer | Marks | Guidance |
|--------|-------|----------|
| Example diagrams showing x marks arranged vertically with circled symbol | M1 A1 A1 | |2 Fig. 2.1 represents the two floors of a house. There are 5 rooms shown, plus a hall and a landing, which are to be regarded as separate rooms. Each " × " represents an internal doorway connecting two rooms. The " ⊗ " represents the staircase, connecting the hall and the landing.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-3_401_1287_447_388}
\captionsetup{labelformat=empty}
\caption{Fig. 2.1}
\end{center}
\end{figure}
(i) Draw a graph representing this information, with vertices representing rooms, and arcs representing internal connections (doorways and the stairs).
What is the name of the type of graph of which this is an example?\\
(ii) A larger house has 12 rooms on two floors, plus a hall and a landing. Each ground floor room has a single door, which leads to the hall. Each first floor room has a single door, which leads to the landing. There is a single staircase connecting the hall and the landing.
How many arcs are there in the graph of this house?\\
(iii) Another house has 12 rooms on three floors, plus a hall, a first floor landing and a second floor landing. Again, each room has a single door on to the hall or a landing. There is one staircase from the hall to the first floor landing, and another staircase joining the two landings.
How many arcs are there in the graph of this house?\\
(iv) Fig. 2.2 shows the graph of another two-floor house. It has 8 rooms plus a hall and a landing. There is a single staircase.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-3_208_666_1896_694}
\captionsetup{labelformat=empty}
\caption{Fig. 2.2}
\end{center}
\end{figure}
Draw a possible floor plan, showing internal connections.
\hfill \mbox{\textit{OCR MEI D1 2006 Q2 [8]}}