COS 226 Exercises on Maximum Flow (4 exercises)

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.

Give a maxflow formulation that determines a distribution that satisfies the demands of a maximum number of patients.

1. Draw a directed graph model 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 (named 0), a supply node for each of the four blood types (named 1 to 4 for A, B, O, and AB, respectively), a demand node for each blood type (named 5 to 8 for A, B, O, and AB, respectively), and a sink (named 9).

2. Solve the maxflow 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 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 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.