5.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{6b51f3a0-0945-4254-8c63-20e1371e9e3a-06_648_567_273_750}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\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$$
\begin{enumerate}[label=(\alph*)]
\item Use this information to deduce the initial matching.
\item Find the third alternating path that starts at C .
\item List the improved matching generated by using the alternating path $\mathrm { C } - 3 = \mathrm { S } - 4 = \mathrm { D } - 5$
\item 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)
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2018 Q5 [6]}}