3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e02c4a9a-d2ab-489f-b838-9b4d902c4457-4_743_457_237_434}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e02c4a9a-d2ab-489f-b838-9b4d902c4457-4_743_455_237_1165}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
Define the terms
- bipartite graph,
- matching.
Figure 3 shows the possible allocations of six people, Charles (C), Emily (E), George (G), Harriet (H), Jack (J) and Shen (S), to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 4 shows an initial matching.
- Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you use and state your improved matching.
Emily has task 5 added to her possible allocations and Harriet has task 3 added to her possible allocations.
- Starting from the improved matching found in part (c), use the maximum matching algorithm to find a complete matching. You should list the alternating path you use and state your improved matching.
(3)
(Total 10 marks)