Physical space modeling

6 The Devil's Dice are four cubes with faces coloured green, yellow, blue or red.
Cube 1 has three green faces and one each of yellow, blue and red.

• Two of the green faces are opposite one another.
• The other green face is opposite the yellow face.
• The blue face is opposite the red face.

This information is represented using the graph in Fig. 1. \begin{figure}[h] \end{figure} Fig. 1

1. Cube 2 has a green face opposite a blue face, another green face opposite a red face and a second red face opposite a yellow face. Draw a graph to represent this information. The graph in Fig. 2 represents opposite faces in cube 3. Cube 3 \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_350_326_1398_986} \captionsetup{labelformat=empty} \caption{Fig. 2}
   \end{figure}
2. How many yellow faces does cube 3 have? Cube 4 has one green face, two yellow faces, one blue face and two red faces. The graph in Fig. 3 is an incomplete representation of opposite faces in cube 4 . \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Cube 4} \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_257_273_2115_1018}
   \end{figure} Fig. 3
3. Complete the graph in your answer book. The Devil's Dice puzzle requires the cubes to be stacked to form a tower so that each long face of the tower uses all four colours. The puzzle can be solved using graph theory. First the graphs representing the opposite faces of the four cubes are combined into a single graph. The edges of the graph are labelled \(1,2,3\) or 4 to show which cube they belong to. The labelled graph in Fig. 4 shows cube 1 and cube 3 together. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-09_630_689_625_689} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Complete the copy of the labelled graph in your answer book to show all four cubes. A subgraph is a graph contained within a given graph.
   From the graph representing all four cubes a subgraph needs to be found that will represent the front and back faces of the tower. Each face of the tower uses each colour once. This means that the graph representing the front and back faces must be a subgraph of the answer to part (iv) with four edges labelled \(1,2,3\) and 4 and four nodes each having order two.
5. Explain why if the loop labelled 1 joining G to G is used, it is not possible to form a subgraph with four edges labelled 1, 2, 3 and 4 and nodes each having order two. Suppose that the edge labelled 1 that joins B and R is used.
6. Draw a subgraph that has the required properties and uses the edge labelled 1 that joins B and R .
7. Using your answer to part (vi), show the two possible colourings of the back of the tower.

1 The diagram shows an electrical circuit with wires and switches and with five components, labelled A, B, C, D and E. \includegraphics[max width=\textwidth, alt={}, center]{11c2d98f-1f72-4f1b-b971-5521bee09358-2_328_730_609_319} \includegraphics[max width=\textwidth, alt={}, center]{11c2d98f-1f72-4f1b-b971-5521bee09358-2_261_519_621_1224}

1. Draw a graph showing which vertices are connected together, either directly or indirectly, when the two switches remain open.
2. How many arcs need to be added to your graph when both switches are closed? The graph below shows which components are connected to each other, either directly or indirectly, for a second electrical circuit. \includegraphics[max width=\textwidth, alt={}, center]{11c2d98f-1f72-4f1b-b971-5521bee09358-2_410_494_1356_788}
3. Find the minimum number of arcs which need to be deleted to create two disconnected sets of vertices, and write down your two separate sets.
4. Explain why, in the second electrical circuit, it might be possible to split the components into two disconnected sets by cutting fewer wires than the number of arcs which were deleted in part (iii).

1 A graph is obtained from a solid by producing a vertex for each exterior face. Vertices in the graph are connected if their corresponding faces in the original solid share an edge. The diagram shows a solid followed by its graph. The solid is made up of two cubes stacked one on top of the other. This solid has 10 exterior faces, which correspond to the 10 vertices in the graph. (Note that in this question it is the exterior faces of the cubes that are being counted.) \includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_455_309_571_653} \includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_444_286_573_1135}

1. Draw the graph for a cube.
2. Obtain the number of vertices and the number of edges for the graph of three cubes stacked on top of each other. \includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_643_305_1302_881}

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] \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.

1 The numbers on opposite faces of the die shown (a standard die) add up to 7. The adjacency graph for the die is a graph which has vertices representing faces. In the adjacency graph two vertices are joined with an arc if they share an edge of the die. For example, vertices 2 and 6 are joined by an arc because they share an edge of the die. \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-2_246_213_488_1608}

1. List the pairs of numbers which are opposite each other.
2. Draw the adjacency graph.
3. Identify and sketch a solid which has the following adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-2_287_307_1027_879}

3 The adjacency graph of a cube \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_106_108_214_735}
is shown. Vertices on the graph represent faces of the cube. Two vertices are connected by an arc if the corresponding faces of the cube share an edge. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_401_464_246_1334} The second graph is the complement of the adjacency graph, i.e. the graph that consists of the same vertices together with the arcs that are not in the adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_403_464_737_1334} Throughout this question we wish to colour solids so that two faces that share an edge have different colours. The second graph shows that the minimum number of colours required for a cube is three, one colour for the top and base, one for the front and back, and one for the left and right.

1. Draw the adjacency graph for a square-based pyramid, and draw its complement. Hence find the minimum number of colours needed to colour a square-based pyramid. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_161_202_1434_1548}
2. (A) Draw the adjacency graph for an octahedron, and draw its complement.
   (B) An octahedron can be coloured using just two colours. Explain how this relates to the complement of the adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_227_205_1731_1548}

2 Answer this question on the insert provided. A maze is constructed by building east/west and north/south walls so that there is a route from the entrance to the exit. The maze is shown in Fig. 2.1. \begin{figure}[h] \end{figure} On entering the maze Janet says "I'm always going to keep a hand in contact with the wall on the right." John says "I'm always going to keep a hand in contact with the wall on the left."

1. On the insert for this question show Janet's route through the maze. On the insert show John's route.
2. Will these strategies always find a way through such mazes? Justify your answer. In some mazes the objective is to get to a marked point before exiting. An example is shown in Fig. 2.2, where \(\mathbf { X }\) is the marked point. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-3_497_716_1672_669} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} In the maze shown in Fig. 2.2 Janet's algorithm takes her to \(\mathbf { X }\). John's algorithm does not take him to \(\mathbf { X }\). John modifies his algorithm by saying that he will turn his back on the exit if he arrives there without visiting \(\mathbf { X }\). He will then move onwards, continuing to keep a hand in contact with the wall on the left.
3. Will this modified algorithm take John to the point \(\mathbf { X }\) in the maze in Fig. 2.2?
4. Will this modified algorithm take John to any marked point in the maze in Fig. 2.2? Justify your answer.

1 The adjacency graph for a map has a vertex for each country. Two vertices are connected by an arc if the corresponding countries share a border.

1. Draw the adjacency graph for the following map of four countries. The graph is planar and you should draw it with no arcs crossing. \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_531_1486_561_292}
2. Number the regions of your planar graph, including the outside region. Regarding the graph as a map, draw its adjacency graph.
3. Repeat parts (i) and (ii) for the following map. \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_533_1484_1361_294}

Each of the following symbols consists of boundaries enclosing regions. \includegraphics{figure_1} The symbol representing zero has three regions, the outside, that between the two boundaries and the inside. To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for \includegraphics{figure_2} is \(\bullet \longrightarrow \bullet \longrightarrow \bullet\).

1. Produce the graph for the symbol \includegraphics{figure_3}. [1]
2. Give two symbols each having the graph \(\bullet \longrightarrow \bullet\). [2]
3. Produce the graph for the symbol \includegraphics{figure_4}. [2]
4. Produce a single graph for the composite symbol \includegraphics{figure_5}. [2]
5. Give the name of a connected graph with \(n\) nodes and \(n - 1\) arcs. [1]