2.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-2_432_579_1206_395}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{be646775-535e-4105-86b4-ffc7eda4fa51-2_430_579_1208_1096}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Five tour guides, Alice, Emily, George, Rose and Weidi, need to be assigned to five coach trips, 1, 2, 3, 4 and 5 . A bipartite graph showing their preferences is given in Figure 1 and an initial matching is given in Figure 2.
- Use the maximum matching algorithm, starting with vertex G , to increase the number of matchings. State the alternating path you used.
- List the improved matching you found in (a).
- Explain why a complete matching is not possible.
Weidi agrees to be assigned to coach trip 3, 4 or 5.
- Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching.
(3)