- (a) Define the term 'bipartite graph'.
Six workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , are to be matched to six tasks, 1, 2, 3, 4, 5 and 6
The table below shows the tasks that each worker is able to do.
| Worker | Tasks |
| \(A\) | 2,4 |
| \(B\) | 5 |
| \(C\) | 3,4 |
| \(D\) | 2 |
| \(E\) | \(4,5,6\) |
| \(F\) | 1,6 |
(b) Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocation of workers to tasks.
(1)
Initially, workers \(\mathrm { A } , \mathrm { C } , \mathrm { E }\) and F are allocated to tasks 2, 4, 5 and 6 respectively.
(c) Starting from the given initial matching, apply the maximum matching algorithm to obtain a complete matching. You must state the alternating paths that you use, and state your improved matching after each iteration.