4. This question should be answered on the sheet provided.
The manager of an outdoor centre must staff each activity offered by the centre with an appropriately qualified instructor. The table below shows the sports for which each member of staff is qualified to supervise.
| Name | Activities |
| Fatima | Windsurfing, Sailing |
| Gavin | Climbing, Orienteering |
| Hassan | Windsurfing, Climbing |
| Iain | Sailing, Diving |
| Jane | Diving, Sailing, Orienteering |
- Draw a bipartite graph to model this situation.
Initially the manager allocates Fatima, Gavin, Iain and Jane to supervise the first sport listed against their names in the table.
- Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how you have applied the algorithm.
(6 marks)