2The Max Flow ProblemG = (N,A)xij= flow on arc (i,j)uij= capacity of flow in arc (i,j)s = source nodet = sink nodeMaximize vSubject to jxij- kxki= 0 for each i ! s,t jxsj= v0 " xij" uijfor all (i,j) # A.3Maximum FlowsWe refer to a flow x as maximum if it is feasible and maximizes v. Our objective in the max flow problem is to find a maximum flow.s12t10,88,71,110,66, 5A max flow problem. Capacities and a non-optimum flow.8The Residual Networks12t10,88,71,110,66, 5i jxuijiji ju - xxijijijs12t211418567We let rijdenotetheresidualcapacityof arc (i,j)The Residual Network G(x)9A Useful Idea: Augmenting PathsAn augmenting path is a path from s to t in the residual network.The residual capacity of the augmenting path P is $(P) = min{rij: (i,j) # P}.Toaugment along P is to send d(P) units of flow along each arc of the path. We modify x and the residual capacities appropriately.rij:= rij- $(P) and rji:= rji+ $(P) for (i,j) # P.s12t211418567s12t214866810The Ford Fulkerson Maximum Flow AlgorithmBeginx := 0;create the residual network G(x);while there is some directed path from s to t in G(x) dobeginlet P be a path from s to t in G(x);%:= $(P);send %units of flow along P; update the r's;endend {the flow x is now maximum}.Ford-FulkersonAlgorithmAnimation11Proof of Correctness of the AlgorithmAssume that all data are integral.Lemma: At each iteration all residual capacities are integral.Proof. It is true at the beginning. Assume it is true after the first k-1 augmentations, and consider augmentation k along path P.The residual capacity %of P is the smallest residual capacity on P, which is integral.After updating, we modify residual capacities by 0, or %, and thus residual capacities stay integral.12Theorem. The Ford-Fulkerson Algorithm is finiteProof. The capacity of each augmenting path is at least 1.The augmentation reduces the residual capacity of some arc (s, j) and does not increase the residual capacity of (s, i) for any i.So, the sum of the residual capacities of arcs out of s keeps decreasing, and is bounded below by 0.Number of augmentations is O(nU), where U is the largest capacity in the network.13How do we know when a flow is optimal?s12t10,98,81,110,76, 6METHOD 1. There is no augmenting path in the residual network.s12t1817693reachablefrom s in G(x)not reachable from s in G(x)14Method 2: Cut Duality Theorys12t10,98,81,110,76, 6An (s,t)-cut in a network G = (N,A) is a partition of N into two disjoint subsets S and T such that s #Sand t # T, e.g., S = { s, 1 } and T = { 2, t }.Thecapacity of a cut (S,T) isCAP(S,T) = &i#S&j#Tuij15Weak Duality Theorem for the Max Flow ProblemTheorem. If x is any feasible flow and if (S,T) is an (s,t)-cut, then the flow v(x) from source to sink in x is at most CAP(S,T).PROOF. We define the flow across the cut (S,T) to beFx(S,T) = &i#S&j#Txij- &i#S&j#Txjis12t10,98,81,110,76, 6If S = {s}, then the flow across (S, T) is 9 + 6 = 15.16Flows Across Cutss12t10,98,81,110,76, 6If S = {s,1}, then the flow across (S, T) is 8+1+6 = 15.s12t10,98,81,110,76, 6If S = {s,2}, then the flow across (S, T) is 9 + 7 - 1 = 15.17More on Flows Across CutsClaim: Let (S,T) be any s-t cut. Then Fx(S,T) = v = flow into t.Proof. Add the conservation of flow constraints for each node i # S - {s} to the constraint that the flow leaving s is v. The resulting equality is Fx(S,T) = v. jxij- kxki= 0 for each i #S\s jxsj= vi ji # Sj #Txiji ji # Tj #S-xij18More on Flows Across CutsClaim: The flow across (S,T) is at most the capacity of a cut.Proof. If i # S, and j # T, then xij"' uij. If i # T, and j #S, then xij'(' 0.Fx(S,T) = &i#S&j#Txij- &i#S&j#TxjiCap(S,T) = &i#S&j#Tuij- &i#S&j#T019Max Flow Min Cut TheoremTheorem. (Optimality conditions for max flows). The following are equivalent.1. A flow x is maximum.2. There is no augmenting path in G(x).3. There is an s-t cutset (S, T) whose capacity is the flow value of x.Corollary. (Max-flow Min-Cut). The maximum flow value is the minimum value of a cut.Proof of Theorem. 1 ) 2. (not 2 ) not 1)Suppose that there is an augmenting path in G(x). Then x is not maximum.20Continuation of the proof.3 ) 1. Let v = Fx(S, T) be the flow from s to t. By assumption, v = CAP(S, T). By weak duality, the maximum flow is at most CAP(S, T). Thus the flow is maximum.2 ) 3. Suppose there is no augmenting path in G(x).Claim: Let S be the set of nodes reachable from s in G(x). Let T = N\S. Then there is no arc in G(x) from S to T.Thus i #'S and j # T ) xij= uiji #T and j # S ) xij= 0.21Final steps of the proofThus i #'S and j # T ) xij= uiji #T and j # S ) xij= 0.Set SSet T1 23 4s tThere is no arc from S to T in G(x)x12= u12x43= 0If follows that Fx(S,T) = &i#S&j#Txij- &i#S&j#Txji= &i#S&j#Tuij- &i#S&j#T0 = CAP(S,T)22ReviewCorollary. If the capacities are finite integers, then the Ford-Fulkerson Augmenting Path Algorithm terminates in finite time with a maximum flow from s to t.Corollary. If the capacities are finite rational numbers, then the Ford-Fulkerson Augmenting Path Algorithm terminates in finite time with a maximum flow from s to t. (why?)Corollary. To obtain a minimum cut from a maximum flow x, let S denote all nodes reachable from s in G(x).Remark. This does not establish finiteness if uij= *or if capacities may be irrational.23A simple and very bad examples12tM MMM124After 1 augmentations12tM-1 MM-1M11125After two augmentationss12tM-1 M-1M-1M-11111126After 3 augmentationss12tM-2 M-1M-2M-11221127And so on28After 2M
View Full Document
Unlocking...