- Explain what is meant by a planar graph.
(Total 2 marks)
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{0fdc5a3c-97e7-46e3-a57c-45a13755f0e5-2_751_654_552_349}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{0fdc5a3c-97e7-46e3-a57c-45a13755f0e5-2_769_663_543_1151}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Six workers, Annie, Emma, Hannah, Jerry, Louis and Morand, are to be assigned to five tasks, 1,2,3,4 and 5.
For safety reasons, task 1 must be done by two people working together.
A bipartite graph showing the possible allocations of the workers is given in Figure 1 and an initial matching is given in Figure 2.
The maximum matching algorithm will be used to obtain a complete matching.
- Although there are five tasks, six vertices have been created on the right hand side of each bipartite graph. Explain why this is necessary when applying this algorithm.
- Find an alternating path and the complete matching it gives.
Hannah is now unable to do task 5 due to health reasons.
- Explain why a complete matching is no longer possible.