Maximum matching algorithm application

\includegraphics{figure_3} \includegraphics{figure_4} A film critic, Verity, must see five films A, B, C, D and E over two days. The films are being shown at five special critics' preview times: \begin{align} 1 &\text{ (Monday 4 pm),}
2 &\text{ (Monday 7 pm),}
3 &\text{ (Tuesday 1 pm),}
4 &\text{ (Tuesday 4 pm),}
5 &\text{ (Tuesday 7 pm).} \end{align} The bipartite graph in Figure 3 shows the times at which each film is showing. Initially Verity intends to see \begin{align} &\text{Film A on Monday at 4 pm,}
&\text{Film B on Tuesday at 4 pm,}
&\text{Film C on Tuesday at 1 pm,}
&\text{Film D on Monday at 7 pm.} \end{align} This initial matching is shown in Figure 4. Using the maximum matching algorithm and the given initial matching,

1. find two distinct alternating paths and complete the matchings they give. [6]

Verity's son is very keen to see film D, but he can only go with his mother to the showing on Monday at 7 pm.

1. Explain why it will not be possible for Verity to take her son to this showing and still see all five films herself. [2]

(Total 8 marks)

\includegraphics{figure_1} \includegraphics{figure_2} 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.

1. 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. [2]
2. Find an alternating path and the complete matching it gives. [3]

Hannah is now unable to do task 5 due to health reasons.

1. Explain why a complete matching is no longer possible. [2]

(Total 7 marks)

\includegraphics{figure_3} \includegraphics{figure_4} Figure 3 shows the possible allocations of six people, Amelia, Charlie, Ellie, Gemma, Jimmy and Saskia, to six tasks, 1, 2, 3, 4, 5 and 6. Figure 4 shows an initial matching.

1. Use the maximum matching algorithm once to find an improved matching. You must state the alternating path used and your improved matching. [3]
2. Explain why a complete matching is not possible. [2] After training, Jimmy can be assigned to tasks 4 or 5 and Ellie to tasks 2, 3, 5 or 6.
3. Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path used and your final matching. [3]

(Total 8 marks)

This question should be answered on the sheet provided. There are 5 computers in an office, each of which must be dedicated to a single application. The computers have different specifications and the following table shows which applications each computer is capable of running.

1. Draw a bipartite graph to model this situation. [1 mark]

Initially it is decided to run the Office application on computer \(F\), Animation on computer \(H\), and Data on computer \(I\).

1. Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied. [9 marks]
2. Computer \(H\) is upgraded to allow it to run CAD. Find an alternative matching to that found in part (b). [3 marks]