Only need help with part (c) and part (d)

only need help with part (c) and part (d)

Problem 3. k departments of some University nominate professors to serve on m University committees. For each i = 1,...,k, the ith department nominates Pi professors. Each professor has an appointment only at the Department that nominated him. There cannot be two professors from the same Department on any of the committees. No professor can serve on more than one committee. For each j = 1,...,m, the jth committee has exactly c; members. It is allowed that some professors will not serve on any of the committees at all, but all the vacancies on all the committees must be filled. (a) (4 marks) One would like to know if these committees can be formed in accordance to the rules above. If the answer is yes, one would like to find an assignment of the professors to the committees. Represent this problem as a network flow problem for an appropriate network. (b) (4 marks) Use Max-flow Min-cut theorem to find a system of necessary and sufficient conditions of the existence of the required assignment (of the professors to the committees). Use these conditions to solve the problem in the case, when there are 4 Departments that nominate, correspondingly, 3,1,4,1 professors, and 3 committees, each composed of 3 committee members. composed of 3 committee members. (c) (6 marks) Consider the following modification of the rules above: Now each professor must serve on exactly one committee, but it is allowed if some number of vacancies on each committee remains unfilled. (In other words, C; now serves only as an upper bound for the number of people serving on the jth committee for all j.) Redo (a) and (b) for the new rules. (d) (1 mark) Consider the following modification of the rules: Now each professor must serve on exactly one committee (as in part (c)), but for each j, the jth committee must be composed of exactly c; members (as in parts (a) and (b)). Redo (a) and (b) for these rules. Problem 3. k departments of some University nominate professors to serve on m University committees. For each i = 1,...,k, the ith department nominates Pi professors. Each professor has an appointment only at the Department that nominated him. There cannot be two professors from the same Department on any of the committees. No professor can serve on more than one committee. For each j = 1,...,m, the jth committee has exactly c; members. It is allowed that some professors will not serve on any of the committees at all, but all the vacancies on all the committees must be filled. (a) (4 marks) One would like to know if these committees can be formed in accordance to the rules above. If the answer is yes, one would like to find an assignment of the professors to the committees. Represent this problem as a network flow problem for an appropriate network. (b) (4 marks) Use Max-flow Min-cut theorem to find a system of necessary and sufficient conditions of the existence of the required assignment (of the professors to the committees). Use these conditions to solve the problem in the case, when there are 4 Departments that nominate, correspondingly, 3,1,4,1 professors, and 3 committees, each composed of 3 committee members. composed of 3 committee members. (c) (6 marks) Consider the following modification of the rules above: Now each professor must serve on exactly one committee, but it is allowed if some number of vacancies on each committee remains unfilled. (In other words, C; now serves only as an upper bound for the number of people serving on the jth committee for all j.) Redo (a) and (b) for the new rules. (d) (1 mark) Consider the following modification of the rules: Now each professor must serve on exactly one committee (as in part (c)), but for each j, the jth committee must be composed of exactly c; members (as in parts (a) and (b)). Redo (a) and (b) for these rules