2.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{19cfdf0b-6be6-4f44-bfae-2b6bf592cfd8-2_624_860_1306_610}
\end{figure}
- Starting from \(A\); write down a Hamiltonian cycle for the graph in Figure 1.
- Use the planarity algorithm to show that the graph in Figure 1 is planar.
Arcs \(A F\) and \(E F\) are now added to the graph.
- Explain why the new graph is not planar.
(2)
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{19cfdf0b-6be6-4f44-bfae-2b6bf592cfd8-3_725_1318_266_352}
\end{figure}
Figure 2 models a network of roads which need to be inspected to assess if they need to be resurfaced. The number on each arc represents the length, in km, of that road.
Each road must be traversed at least once and the length of the inspection route must be minimised. - Starting and finishing at \(A\), solve this route inspection problem. You should make your method and working clear. State the length of the shortest route.
(The weight of the network is 77 km .)
Given that it is now permitted to start and finish the inspection at two distinct vertices, - state which two vertices you should choose to minimise the length of the route. Give a reason for your answer.