### COS 226 Exercises on Maximum Flow

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   B   O   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.

1. Give a max flow formulation that determines a distribution that satisfies the demands of a maximum number of patients. Draw the directed graph and put the edge capacity above each edge. Your network should have 10 vertices: a source (named 0), a supply node for each of the four blood types (named 1 to 4), a demand node for each blood type (named 5 to 8), and a sink (named 9).

2. Solve the maximum flow problem using the Ford-Fulkerson augmenting path algorithm. Do the first augmentation on the path 0-2-8-9. (This will force you to use a backwards edge at some point during the rest of the algorithm.) Afterwards, always choose the augmenting path with the fewest number of arcs, 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 arc in the network above.

3. Calculate a min s-t cut in the network above, i.e., list the vertices on the source side of the cut.

4. Use the min cut to deduce a rigorous and concise explanation of why not all of the patients can receive blood from the available supply. Your explanation should be understandable to the hospital administrators who have no knowledge of network flow theory.