3.

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 1}
  \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-3_444_483_401_489}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 2}
  \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-3_444_478_401_1106}
\end{center}
\end{figure}

Five members of staff $1,2,3,4$ and 5 are to be matched to five jobs $A , B , C , D$ and $E$. A bipartite graph showing the possible matchings is given in Fig. 1 and an initial matching $M$ is given in Fig. 2.

There are several distinct alternating paths that can be generated from $M$. Two such paths are

$$2 - B = 4 - E$$

and

$$2 - A = 3 - D = 5 - E$$
\begin{enumerate}[label=(\alph*)]
\item Use each of these two alternating paths, in turn, to write down the complete matchings they generate.

Using the maximum matching algorithm and the initial matching $M$,
\item find two further distinct alternating paths, making your reasoning clear.

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 3}
  \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-4_577_1476_367_333}
\end{center}
\end{figure}

Figure 3 shows the network of paths in a country park. The number on each path gives its length in km . The vertices $A$ and $I$ represent the two gates in the park and the vertices $B , C , D , E , F , G$ and $H$ represent places of interest.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2002 Q3 [6]}}