1 The six cadets in Red Team have been told to guard a building through the night, starting at 2200 hours and finishing at 0800 hours the next day. Each will be on duty for either one hour or three hours and will then hand over to the next cadet.
The table shows which duty each cadet has offered to take.
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Duty start time (24 hour clock time)}
| | 2200 | 0100 | 0200 | 0300 | 0400 | 0500 |
| Amir (A) | | ✓ | ✓ | | | | |
| Becca (B) | | | ✓ | ✓ | | | |
| Chris (C) | | | | ✓ | ✓ | ✓ | |
| Dan (D) | | | | | | ✓ | ✓ |
| Emma (E) | | | ✓ | | | ✓ | |
| Finn \(( F )\) | | ✓ | | | | | |
\end{table}
- Draw a bipartite graph to represent this information.
Amir suggests that he should take the 2200 duty, hand over to Becca at 0100 , she can hand over to Chris at 0200 , and Dan can take the 0400 duty. However, this leaves Emma and Finn to cover the 0300 and 0500 duties, and neither of them wants either of these.
- Write down the shortest possible alternating path starting at the 0500 duty and hence write down an improved but still incomplete matching between the cadets and the duties.
- Augment this second incomplete matching by writing down a shortest possible alternating path, this time starting from one of the cadets, to form a complete matching between the cadets and the duties. Write down which cadet should take which duty.