Themaxflowproblem.pptVIP

The max flow problem Ford-Fulkerson method Ford-Fulkerson(G) f = 0 while(9 simple path p from s to t in Gf) f := f + fp output f A cut Lemma 26.5 + Corollary 26.6 Let f be a flow in G and let (S,T) be a cut in G. Then |f| = f(S,T). Let f be a flow in G and let (S,T) be a cut in G. Then |f| · c(S,T). This is a weak duality theorem. Max Flow – Min Cut Theorem Let f be a flow in G. The following three conditions are equivalent: 1. f is a maximum flow 2. Gf contains no augmenting path 3. There is a cut (S,T) so that |f|=c(S,T) Max Flow – Min Cut Theorem The value of the maximum flow in G is equal to the capacity of the minimum cut in G. This is a strong duality theorem. Remarks The solution values agree, not the solutions themselves – flows and cuts are completely different objects. Given a max flow we can easily find a min cut (follows from proof of max flow-min cut theorem). Going the other way is less obvious. Consequence The Ford-Fulkerson method is partially correct, i.e., if it terminates it produces the flow with the maximum value. Local search checklist Design: How do we find the first feasible solution? Neighborhood design? Which neighbor to choose? Analysis: Partial correctness? (termination )correctness) Termination? Complexity? Termination Suppose all capacities are integers. We start with a flow of value 0. In each iteration, we get a new flow with higher integer value. We always have a legal flow, i.e., one of value at most |f|. Hence we can have at most |f| iterations. Correctness of Ford-Fulkerson Since Ford-Fulkerson is partially correct and it terminates if capacities are integers it is a correct algorithm for finding the maximum flow if capacities are integers. Exercise: It is also correct if capacities are rationals. Does Ford-Fulkerson always terminate? In case of irrational capacities, not necessarily! (Exercise) But we can’t give irrational capacities as inputs to digital computers anywa