NAMES:

PRECEPTS:

LOGINS:

COS 226 Exercises on Maxflow

Reference: pp. 886–902 in Algorithms, 4th edition.


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 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).






















2. 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.






3. Calculate a mincut in the flow network above, i.e., list the vertices on the source side of the cut.







4. Using the mincut, explain in nontechnical terms (using only grade-school arithmetic) why why not all of the patients can receive blood from the available supply. Your explanation should be rigorous and understandable to the hospital administrators who have no knowledge of maxflow-mincut theory.