The department has s students S1,..., S. looking for a thesis topic. There are t open thesis topics T1,...,It. For each thesis topic, there is at least one student qualified for it and each student is qualified for at least one topic. Each topic is offered by exactly one of ther research groups R1,..., R. Each student must pick a thesis topic he is qualified for. No two students may pick the same topic and research group i can take care of at most ui students. Given full information about students, topics and research groups, is there a way to distribute the thesis topics? 1. Show how to formulate the above problem as a Maximum Flow Problem. Explain the different elements of your construction. 2. Given an integral maximum flow in your network, show how to determine whether a distribution scheme as desired is possible. Also explain how to obtain a valid distribution scheme, if one exists from a maximum flow in your network. Finally, show that given distribution scheme, you can construct a corresponding flow in the network. The department has s students S1,..., S. looking for a thesis topic. There are t open thesis topics T1,...,It. For each thesis topic, there is at least one student qualified for it and each student is qualified for at least one topic. Each topic is offered by exactly one of ther research groups R1,..., R. Each student must pick a thesis topic he is qualified for. No two students may pick the same topic and research group i can take care of at most ui students. Given full information about students, topics and research groups, is there a way to distribute the thesis topics? 1. Show how to formulate the above problem as a Maximum Flow Problem. Explain the different elements of your construction. 2. Given an integral maximum flow in your network, show how to determine whether a distribution scheme as desired is possible. Also explain how to obtain a valid distribution scheme, if one exists from a maximum flow in your network. Finally, show that given distribution scheme, you can construct a corresponding flow in the network