4. (a) Define the term 'alternating path'.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-6_469_647_315_708}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
Figure 4 shows the possible allocations of five people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , to five tasks, \(1,2,3,4\) and 5
An initial matching has three people allocated to three of the tasks.
Starting from this initial matching, one possible alternating path that starts at E is
$$E - 2 = B - 3 = A - 4 = D - 1$$
(b) Use this information to
- deduce this initial matching,
- list the improved matching generated by the given alternating path.
(c) Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path you use and the final matching.