(a) Define the terms
- alternating path,
- matching.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-2_568_621_689_344}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-2_554_540_701_1171}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
At a school fair, five teachers, \(A , B , C , D\) and \(E\), are to supervise five stalls, \(1,2,3,4\) and 5 .
A bipartite graph showing their possible allocations is given in Figure 1. An initial matching is given in Figure 2.
(b) Use the maximum matching algorithm twice to obtain a complete matching. List clearly the alternating paths you use.