1.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-02_476_727_210_683}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
Figure 1 shows the graph G.
- State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer.
- Write down an example of a Hamiltonian cycle on G.
- State whether or not G is planar, justifying your answer.
- 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. - 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}
- Perform the final iteration of Floyd's algorithm that follows from Table 1, showing the time matrix for this iteration.