You are organizing a dinner with n di erent groups of friends, with each group composed of gi members with i 2 f1; : : : ; ng. you have m tables each for r people, and you want want to impose that all friends from the same group should be seated in di erent tables. in this way you will obligate your friends ( nally) to chat with people who does not belong to their closest groups. show (graphically) that using a maximum ow formulation we can nd a feasible arrangement of friends to tables that satisfy the rule mentioned above, or show that it is not possible. hint: imagine that someone solves the maximum flow problem (that you need to find)
and tells you what's the maximum flow. using that number, how can you know if it
was possible to nd the arrangement suggested in the problem statement or not.