1 Six people, \(A , B , C , D , E\) and \(F\), are to be matched to six tasks, \(1,2,3,4,5\) and 6 . The following adjacency matrix shows the possible matching of people to tasks.
| Task 1 | Task 2 | Task 3 | Task 4 | Task 5 | Task 6 |
| A | 0 | 1 | 0 | 1 | 0 | 0 |
| B | 1 | 0 | 1 | 0 | 1 | 0 |
| \(\boldsymbol { C }\) | 0 | 0 | 1 | 0 | 1 | 1 |
| D | 0 | 0 | 0 | 1 | 0 | 0 |
| E | 0 | 1 | 0 | 0 | 0 | 1 |
| \(\boldsymbol { F }\) | 0 | 0 | 0 | 1 | 1 | 0 |
- Show this information on a bipartite graph.
- At first \(F\) insists on being matched to task 4. Explain why, in this case, a complete matching is impossible.
- To find a complete matching \(F\) agrees to be assigned to either task 4 or task 5.
Initially \(B\) is matched to task 3, \(C\) to task 6, \(E\) to task 2 and \(F\) to task 4.
From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.