1.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-2_536_476_319_434}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-2_536_474_319_1146}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
A delivery firm has six vans, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , available for six deliveries, \(1,2,3,4,5\) and 6 . Each van must be assigned to just one delivery.
The bipartite graph shown in Figure 1 shows the possible matchings and Figure 2 shows an initial matching.
A complete matching is required, starting from the given initial matching.
- Explain why it is necessary to use the maximum matching algorithm twice.
There are three possible alternating paths that start at either D or B . One of these is
$$D - 2 = A - 3 = F - 6 = E - 5$$
- Find the other two alternating paths.
- List the improved matching generated by using the alternating path
$$D - 2 = A - 3 = F - 6 = E - 5$$
- Starting from the improved matching found in (c), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use and your complete matching.