- Ann, Bryn, Daljit, Gareth and Nickos have all joined a new committee. Each of them is to be allocated to one of five jobs \(1,2,3,4\) or 5 . The table shows each member's preferences for the jobs.
| Ann | 1 or 2 |
| Bryn | 3 or 1 |
| Daljit | 2 or 4 |
| Gareth | 5 or 3 |
| Nickos | 1 or 2 |
Initially Ann, Bryn, Daljit and Gareth are allocated the first job in their lists shown in the table.
- Draw a bipartite graph to model the preferences shown in the table and indicate, in a distinctive way, the initial allocation of jobs.
- Use the matching improvement algorithm to find a complete matching, showing clearly your alternating path.
- Find a second alternating path from the initial allocation.