3. This question should be answered on the sheet provided.
A firm of auditors is to place one trainee accountant at each of its five offices. These are situated in Dundee, Edinburgh, Glasgow and London. There are two offices in London, one of which is the company's Head Office.
The table summarises the trainees’ preferences.
| Trainee | Preferences |
| \(P\) | Dundee, London (either) |
| \(Q\) | Dundee, Edinburgh, Glasgow |
| \(R\) | Glasgow, London (Head Office only) |
| S | Edinburgh |
| \(T\) | Edinburgh |
- Draw a bipartite graph to model this situation.
- Explain why no complete matching is possible.
Trainee \(T\) is persuaded that either office in London would be just as good for her personal development as the Edinburgh office.
- Draw a second bipartite graph to model the changed situation.
In an initial matching, trainee \(P\) is placed in the Dundee office, trainee \(R\) in the Glasgow office, and trainee \(S\) in the Edinburgh office.
- Draw this initial matching.
- Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must indicate how the algorithm has been applied, stating clearly the alternating paths you use and the final matching.
(7 marks)
Turn over