Multiple choice identification

2. Explain what is meant, in a network, by (a) a walk, (b) a tour.
(2) (2) (Total 4 marks)

1 Which of the following graphs is not planar? Circle your answer.
[0pt] [1 mark] \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_186_301_1000_520} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_218_224_986_884} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_241_236_982_1201} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_241_241_982_1521}

1. \begin{figure}[h] \end{figure} Figure 1 shows the graph G.

1. State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer.
2. Write down an example of a Hamiltonian cycle on G.
3. State whether or not G is planar, justifying your answer.
4. State the number of arcs that would need to be added to G to make the graph \(\mathrm { K } _ { 5 }\) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-03_467_716_178_671} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Direct roads between five villages, A, B, C, D and E, are represented in Figure 2. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the five villages.
5. For the network represented in Figure 2, complete the initial time matrix in the answer book. The time matrix after four iterations of Floyd's algorithm is shown in Table 1. \begin{table}[h]

   	A	B	C	D	E
   A	-	10	13	15	5
   B	10	-	3	5	4
   C	13	3	-	2	7
   D	15	5	2	-	7
   E	5	4	7	7	-

   \captionsetup{labelformat=empty} \caption{Table 1}
   \end{table}
6. Perform the final iteration of Floyd's algorithm that follows from Table 1, showing the time matrix for this iteration.

2 The graph \(G\) has 5 vertices and 6 edges, as shown below. \includegraphics[max width=\textwidth, alt={}, center]{21ed3b4e-a089-4607-b5d6-69d8aac03f31-03_547_547_360_749} Which of the following statements describes the properties of \(G\) ?
Tick ( \(\checkmark\) ) one box. \(G\) is Eulerian and Hamiltonian. □ \(G\) is Eulerian but not Hamiltonian. □ \(G\) is semi-Eulerian and Hamiltonian. □ \(G\) is semi-Eulerian but not Hamiltonian. □

2 The graph \(D\) is shown in the diagram below. \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_115_150_1756_945} Which of the graphs below is a subdivision of \(D\) ?
Circle your answer. \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_218_154_2124_534} \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_208_150_2129_808} \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_208_154_2129_1082} \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_208_149_2129_1361}

A connected planar graph has \(v\) vertices, \(e\) edges and \(f\) faces. Which one of the formulae below is correct? Circle your answer. [1 mark] \(v + e + f = 2\) \quad\quad \(v - e + f = 2\) \quad\quad \(v - e - f = 2\) \quad\quad \(v + e - f = 2\)

Which one of the graphs shown below is semi-Eulerian? Tick (\(\checkmark\)) one box. [1 mark] \includegraphics{figure_3}

The graph \(G\) has a subgraph isomorphic to \(K_5\), the complete graph with 5 vertices. Which of the following statements about \(G\) must be true? Tick \((\checkmark)\) one box. [1 mark] \(G\) is not connected \(G\) is not Hamiltonian \(G\) is not planar \(G\) is not simple

The simple-connected graph \(G\) has the adjacency matrix $$\begin{array}{c|cccc} & A & B & C & D \\ \hline A & 0 & 1 & 1 & 1 \\ B & 1 & 0 & 1 & 0 \\ C & 1 & 1 & 0 & 1 \\ D & 1 & 0 & 1 & 0 \\ \end{array}$$ Which one of the following statements about \(G\) is true? Tick \((\checkmark)\) one box. [1 mark] \(G\) is a tree \(\square\) \(G\) is complete \(\square\) \(G\) is Eulerian \(\square\) \(G\) is planar \(\square\)