4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-4_549_586_285_356}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-4_545_583_287_1128}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
Six airline pilots, Alice, Dan, Miya, Phil, Sophie and Tom, are to be assigned to six flights, 1, 2, 3, 4, 5 and 6. A bipartite graph showing the possible allocations is shown in Figure 2, and an initial matching is given in Figure 3.
The maximum matching algorithm will be used to obtain a complete matching.
- Starting from A, find an alternating path that leads to an improved matching and list the improved matching that it gives.
(3) - Using the improved matching found in part (a) as the new initial matching, find a complete matching. You must state any alternating paths you use and list your final complete matching.