5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{6b51f3a0-0945-4254-8c63-20e1371e9e3a-06_648_567_273_750}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
Figure 3 shows the possible allocations of five workers, Cole (C), Dorothy (D), Harold (H), Richard (R) and Stephen (S), to five tasks, 1, 2, 3, 4 and 5.
In an initial matching, each of three workers is allocated to a different task.
For this initial matching, there are three possible alternating paths that start at C .
One alternating path is
$$C - 3 = S - 4 = D - 5$$
A second alternating path is
$$\mathrm { C } - 1 = \mathrm { H } - 2$$
- Use this information to deduce the initial matching.
- Find the third alternating path that starts at C .
- List the improved matching generated by using the alternating path \(\mathrm { C } - 3 = \mathrm { S } - 4 = \mathrm { D } - 5\)
- Starting from the improved matching found in (c), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path you use and the final matching.
(3)