1.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{fd0401c4-bf18-4c3b-af1d-cd1b633c6853-2_791_452_436_483}
\end{figure}
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{fd0401c4-bf18-4c3b-af1d-cd1b633c6853-2_796_465_433_1226}
\end{figure}
A taxi firm has six taxis \(A , B , C , D , E\) and \(F\), available for six journeys, \(1,2,3,4,5\) and 6 , which are booked for 9 a.m. tomorrow.
The bipartite graph shown in Figure 1 shows the possible matchings.
Initially \(A\), \(B\), \(C\) and \(D\) are matched to 5, 2, 3 and 6 respectively, as indicated in Figure 2.
- Explain why it is necessary to perform the maximum matching algorithm twice in order to try to obtain a complete matching.
- Use the maximum matching algorithm twice to obtain a complete matching. List clearly the alternating paths you use.
(6)