Question 6: We are given a list of students and classes they are requ…

We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign up for some number of courses. Further, each student needs to sign up for a set number of science courses and humanities courses.

Concretely, suppose you have this input: The classes are Bio101, Bio201, Phil101, and Phil201 (Bio classes are all science and Phil are humanties). The students are Alice and Bob. Every class has a capacity of 3 and each student MUST take exactly 2 science and 2 humanities (4 courses total)

Alice is interested in Bio101, Phil101, and Phill201. Bob is interested in Bio101, Bio201, and Phil101.

The flow network below is the beginning of a reduction to max-flow. The subquestions will ask you to label the graph to finish the reduction and answer a question about the reduction.

In particular, label each node with what it represents in the context of the input above. Some of these labels have been given to you to get you started: e.g, $V_1$ is Alice, $V_3$ is Science, $V_7$ is Bio 101 and $V_2$ is Bob.

(Note: this example may not be satisfiable.)

Based on the above data answer the given subquestions.