4.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{0360f78d-e18c-4c47-a2ec-ddd705a4175f-5_736_602_276_301}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{0360f78d-e18c-4c47-a2ec-ddd705a4175f-5_730_588_278_1171}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}

Six workers, Anthony, Beth, David, Jacob, Kantola and Miri, are to be allocated to six tasks, 1, 2, $3,4,5$ and 6 .

Figure 3 shows the possible allocations of the workers, and an initial matching is shown in Figure 4.
\begin{enumerate}[label=(\alph*)]
\item Write down the technical name given to the type of diagram shown in Figure 3.
\item Use the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and your improved matching.

Anthony now agrees to add task 6 to his possible allocations.
\item Starting with your improved matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and your complete matching.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2011 Q4 [7]}}