Draw the flow network for the problem, putting the edge capacity above each edge, leaving room to fill in flow values later. Your network should have 10 vertices: a source vertex (named 0), a supply vertex for each of the four blood types (named 1 to 4 for A, B, O, and AB, respectively), a demand vertex for each blood type (named 5 to 8 for A, B, O, and AB, respectively), and a sink vertex (named 9).

Solve the maxflow problem using the Ford-Fulkerson augmenting path algorithm. Do the first augmentation using the path 0?2?8?9. Afterwards, always choose the augmenting path with the fewest number of edges, breaking ties in favor of the lexicographically smallest path (e.g., choose 0?2?7?9 over 0?4?6?9). List each of the augmenting paths below. Also, write and circle the final flow values on each edge in the flow network above.

Enthusiastic celebration of a sunny day at a prominent northeastern university has resulted in the arrival at the university's medial clinic of 169 students in need of emergency treatment. Each of the 169 students requires a transfusion of one unit of whole blood. The clinic has supplies of 170 units of whole blood. The number of units of blood available in each of the four major blood groups and the distribution of patients among the groups is summarized below. Blood type A BO AB Supply 46 34 45 45 Demand 39 38 42 50 Type A patients can only receive type A or O; type B patients can receive only type B or O; type O patients can receive only type O; and type AB patients can receive any of the four types. Give a maxflow formulation that determines a distribution that satisfies the demands of a maximum number of patients. Enthusiastic celebration of a sunny day at a prominent northeastern university has resulted in the arrival at the university's medial clinic of 169 students in need of emergency treatment. Each of the 169 students requires a transfusion of one unit of whole blood. The clinic has supplies of 170 units of whole blood. The number of units of blood available in each of the four major blood groups and the distribution of patients among the groups is summarized below. Blood type A BO AB Supply 46 34 45 45 Demand 39 38 42 50 Type A patients can only receive type A or O; type B patients can receive only type B or O; type O patients can receive only type O; and type AB patients can receive any of the four types. Give a maxflow formulation that determines a distribution that satisfies the demands of a maximum number of patients