Abstract shape and algorithm modeling

3 Consider the following algorithm.
Step 1: Input a positive integer \(n\).
Step 2 : Draw a graph consisting of \(n\) vertices and no arcs.
Step 3 : Create a new vertex and join it directly to every vertex of order 0.
Step 4: Create a new vertex and join it directly to every vertex of odd order.
Step 5 : Stop.

1. Draw separate diagrams to show the result of applying this algorithm in the following cases.
   1. \(n = 1\)
   2. \(n = 2\)
   3. \(n = 3\)
   4. \(n = 4\)
   5. State how many arcs are in the graph that results when the algorithm is applied to a set of \(n\) vertices.

2 A tetromino is a two-dimensional shape made by joining four squares edge-to-edge. Joins are along complete edges.

1. Represent each of the tetrominoes below by a graph in which the nodes represent the squares and two nodes are joined by an arc if the squares share a common edge. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_76_268_1206_420} \captionsetup{labelformat=empty} \caption{(A)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_208_1201_836} \captionsetup{labelformat=empty} \caption{(B)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_144_1201_1165} \captionsetup{labelformat=empty} \caption{(C)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_209_1201_1439} \captionsetup{labelformat=empty} \caption{(D)}
   \end{figure}
2. Six simply connected graphs with four nodes are shown below. For each graph, either draw a tetromino that can be represented by the graph, as in part (i), or explain why this is not possible. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_126_1603_299} \captionsetup{labelformat=empty} \caption{(1)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_209_1603_529} \captionsetup{labelformat=empty} \caption{(2)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_125_1603_840} \captionsetup{labelformat=empty} \caption{(3)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_127_1603_1082} \captionsetup{labelformat=empty} \caption{(4)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_122_1603_1343} \captionsetup{labelformat=empty} \caption{(5)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_122_1603_1603} \captionsetup{labelformat=empty} \caption{(6)}
   \end{figure} Two tetrominoes are regarded as being the same if one can be rotated or reflected to form the other. Derek claims that each tetromino corresponds to a unique tree with four nodes, and each tree with four nodes corresponds to a unique tetromino. Derek's claim is wrong.
3. From the diagrams above, find:
   1. a tetromino whose graph does not correspond to a tree;
   2. two different tetrominoes whose graphs correspond to the same tree. A pentomino is a two-dimensional shape made by joining five squares edge-to-edge. Joins are along complete edges. Two pentominoes are regarded as being the same if one can be rotated or reflected to form the other. There are twelve distinct pentominoes.
   3. When the pentominoes are represented by graphs, as in part (i), there are only four distinct graphs. Draw these four graphs.

2 The vertices of a graph are to be coloured using the following rules:

• all vertices are to be coloured
• no two vertices joined by an edge are to have the same colour.

The following graph has been coloured with four colours. \includegraphics[max width=\textwidth, alt={}, center]{71ca9c4e-573b-43b7-910d-4bd610af6b27-2_357_883_1683_591} Kempe's rule allows for colours to be swapped. The rule is:

• choose two colours
• draw the subgraph consisting of the vertices coloured with these two colours, together with the edges that connect them
• in any connected part of this subgraph consisting of two or more vertices, the two colours can be swapped.
  1. Use Kempe's rule, choosing the colours blue and red.

Show that the graph can then be coloured with two colours.

Why does Kempe's rule not constitute an algorithm for colouring graphs?

3 The diagram shows three sets, A, B and C. Each region of the diagram contains at least one element. The diagram shows that B is a subset of \(\mathrm { A } , \mathrm { C }\) is a subset of A , and that B shares at least one element with C . \includegraphics[max width=\textwidth, alt={}, center]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_410_615_342_726} The two graphs below give information about the three sets \(\mathrm { A } , \mathrm { B }\) and C . The first graph shows the relation 'is a subset of' and the second graph shows the relation 'shares at least one element with'. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Draw two graphs to represent the sets \(\mathrm { X } , \mathrm { Y }\) and Z shown in the following diagram. \includegraphics[max width=\textwidth, alt={}, center]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_415_613_1388_731}
2. Draw a diagram to represent the sets \(\mathrm { P } , \mathrm { Q }\) and R for which both of the following graphs apply. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_202_264_1980_621} \captionsetup{labelformat=empty} \caption{'is a subset of'}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_200_260_1982_1155} \captionsetup{labelformat=empty} \caption{'shares at least one element with'}
   \end{figure}

A puzzle involves a 3 by 3 grid of squares, numbered 1 to 9, as shown in Fig. 1a below. Eight of the squares are covered by blank tiles. Fig. 1b shows the puzzle with all of the squares covered except for square 4. This arrangement of tiles will be called position 4. \includegraphics{figure_1} A move consists of sliding a tile into the empty space. From position 4, the next move will result in position 1, position 5 or position 7.

1. Draw a graph with nine vertices to represent the nine positions and arcs that show which positions can be reached from one another in one move. What is the least number of moves needed to get from position 1 to position 9? [3]
2. State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is. [2]