(a) Define the terms
- bipartite graph,
- alternating path.
(4)
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-02_624_526_653_347}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-02_611_519_662_1192}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
At a hotel, six guests, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , are to be allocated to six rooms, \(1,2,3,4,5\) and 6 . Each room needs to be allocated to exactly one guest.
A bipartite graph showing their possible allocations is given in Figure 1. An initial matching is given in Figure 2.
(b) Starting from the initial matching given in Figure 2, apply the maximum matching algorithm to find an alternating path from F to 5 . Hence find an improved matching. You must list the alternating path that you use and state your improved matching.
(3)
Guest C now has room 5 added to his possible allocations.
(c) Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You must list the alternating path that you use and state your complete matching.