3.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-3_444_483_401_489}
\end{figure}
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-3_444_478_401_1106}
\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$$
- 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\),
- find two further distinct alternating paths, making your reasoning clear.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 3}
\includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-4_577_1476_367_333}
\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.