OCR MEI D1 2006 June — Question 2

Exam BoardOCR MEI
ModuleD1 (Decision Mathematics 1)
Year2006
SessionJune
TopicGraph Theory Fundamentals

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]
\includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-3_401_1287_447_388} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
\end{figure}
  1. 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?
  2. 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?
  3. 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?
  4. 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]
    \includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-3_208_666_1896_694} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
    \end{figure} Draw a possible floor plan, showing internal connections.