2. (a) Define the term 'alternating path'.
(2)
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{2ae673c0-206a-468b-ae6f-ac55e5970f7b-2_813_1262_902_470}
\end{figure}
The bipartite graph in Figure 1 shows the films that six customers wish to hire this Saturday evening. The shop has only one copy of each film. The bold lines indicate an initial matching.
(b) Starting from this initial matching use the maximum matching algorithm twice to obtain a complete matching. You should clearly state the alternating paths you use.
(5)
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{2ae673c0-206a-468b-ae6f-ac55e5970f7b-3_756_1242_302_449}
\end{figure}
Figure 2 shows the network of pipes represented by arcs. The length of each pipe, in kilometres, is shown by the number on each arc. The network is to be inspected for leakages, using the shortest route and starting and finishing at \(A\).
(a) Use the route inspection algorithm to fins which arcs, if any, need to be traversed twice.
[0pt]
(b) State the length of the minimum route. [The total weight of the network is 394 km .]
It is now permitted to start and finish the inspection at two distinct vertices.
(c) State, with a reason, which two vertices should be chosen to minimise the length of the new route.
(2)