CS577 Assignment 9 - Network Flow Solution

Answer the questions in the boxes provided on the question sheets. If you run out of room for an answer, add a page to the end of the document.
Name: 2 Xu Wisc id:
huyan
Network Flow
1. Kleinberg, Jon. Algorithm Design (p. 415, q. 3a) The figure below shows a flow network on which an s t flow has been computed. The capacity of each edge appears as a label next to the edge, and the flow is shown in boxes next to each edge. An edge with no box has no flow being sent down it.

(a) What is the value of this flow?

(b) Please draw the residual graph associated with this flow.

the total flow.
2. Kleinberg, Jon. Algorithm Design (p. 418, q. 8) Consider this problem faced by a hospital that is trying to evaluate whether its blood supply is sufficient:
In a (simplified) model, the patients each have blood of one of four types: A, B, AB, or O. Blood type A has the A antigen, type B has the B antigen, AB has both, and O has neither. Patients with blood type A can receive either A or O blood. Likewise patients with type B can receive either B or O type blood. Patients with type O can only receive type O blood, and patients with type AB can receive any of the four types.
(a) Let sO,sA,sB,sAB denote the hospital’s blood supply on hand, and let dA,dB,dO,dAB denote their projected demand for the coming week. Give a polynomial time algorithm to evaluate whether the blood supply is enough to cover the projected need.
Solution: Mgmt SoSnSnSm do dadr IAB
output boolean variable
ifso do returnfabe ifsatsodosda rewonfake
if SBtSodoadp return fake
if SgtSatsodo do1dB returnfalse
if Igp1 Sats Sododa dB dins returnfalse retune Ture
(b) Network flow is one of the most powerful and versatile tools in the algorithms toolbox, but it can be difficult to explain to people who don’t know algorithms. Consider the following instance. Show that the supply is insufficient in this case, and provide an explanation for this fact that would be understandable to a non-computer scientist. (For example: to a hospital administrator.) Your explanation should not involve the words flow, cut, or graph.
blood type supply demand
O 50 45

3. Kleinberg, Jon. Algorithm Design (p. 419, q. 10) Suppose you are given a directed graph G = (V,E).
This graph has a positive integer capacity0 ce on each edge, a source s 2acyclicV , a sink(no cycles with positivet 2 V . You are also
given a maximum s t flow through G: f. You know that this flow is flow all the way around the cycle), and every flow fe 2 f has an integer value.
Now suppose we pick an edge e⇤ and reduce its capacity by 1 unit. Show how to find a maximum flow in the resulting graph G⇤ in time O(m + n), where n = |V | and m = |E|.
Solution: The maximumflowAMcanstayunchanged or decrease by 1 Simone wehavef 0 Iffley Ce then stayunchange
Tf tie Ceo find aflowonepathfrom t losgothrough e inresidualgraphof
Morespeefically considerek.luv1 leefiel fley thenfind fhowonepathfromU tV adjust f to f Nowwehaveflow f onnewgraphwith flow M I 0 Mtn
Now we trytofindsome augmentingpathfromm s t withnewresidualgraphofflO Mtn
If we can find Maxflowis stillM ifnot wehave th i
4. Kleinberg, Jon. Algorithm Design (p. 420, q. 11) A friend of yours has written a very fast piece of code to calculate the maximum flow based on repeatedly finding augmenting paths. However, you realize that it’s not always finding the maximum flow. Your friend never wrote the part of the algorithm that uses backward edges! So their program finds only augmenting paths that include all forward edges, and halts when no more such augmenting paths remain. (Note: We haven’t specified how the algorithm selects forward-only augmenting paths.)
Is your friend right? Provide a proof supporting your choice.

The input will start with a positive integer, giving the number of instances that follow. For each instance, there will be two positive integers, indicating the number of nodesof edges |E| in the graph. Following this, there will be |E| additional lines describing the edges. Eachn = |V | in the graph and the number edge line consists of a number indicating the source node, a number indicating the destination node, and a capacity. The nodes are not listed separately, but are numbered {1...n}.
Your program should compute the maximum flow value from node 1 to node n in each given graph. A sample input is the following:
2
3 2
2 3 4
1 2 5
6 9
1 2 9
1 3 4
I
2 4 1
2 5 6
3 4 4
3 5 5
4 6 8
5 6 5
5 6 3
The sample input has two instances. For each instance, your program should output the maximum flow on a separate line. Each output line should be terminated by a newline. The correct output for the sample input would be:
4
11