1 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following adjacency matrix shows the tasks that each of the people is able to undertake.
| 1 | 2 | 3 | 4 | 5 | 6 |
| \(\boldsymbol { A }\) | 1 | 0 | 1 | 0 | 0 | 0 |
| \(\boldsymbol { B }\) | 1 | 1 | 0 | 0 | 0 | 1 |
| C | 0 | 1 | 0 | 1 | 0 | 0 |
| \(\boldsymbol { D }\) | 0 | 1 | 0 | 0 | 1 | 0 |
| E | 0 | 0 | 1 | 0 | 1 | 0 |
| F | 0 | 0 | 0 | 0 | 1 | 0 |
- Represent this information in a bipartite graph.
- Initially, \(A\) is assigned to task 3, \(B\) to task 2, \(C\) to task 4 and \(D\) to task 5 .
Use an algorithm from this initial matching to find a maximum matching, listing your alternating paths.