最大流问题的增广路算法概要.pptx

1The max flow problem5102-271945112Ford-Fulkerson methodFord-Fulkerson(G)f=0 while(9 simple path p from s to t in Gf)f:=f+fp output f3STc(S,T)=26A cut4Lemma 26.5+Corollary 26.6Let 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.5Max 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)6Max Flow Min Cut TheoremThe value of the maximum flow in G is equal to the capacity of the minimum cut in G.This is a strong duality theorem.7RemarksThe 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.8ConsequenceThe Ford-Fulkerson method is partially correct,i.e.,if it terminates it produces the flow with the maximum value.9Local search checklistDesign:How do we find the first feasible solution?Neighborhood design?Which neighbor to choose?Analysis:Partial correctness?(termination)correctness)Termination?Complexity?10TerminationSuppose 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.11Correctness of Ford-FulkersonSince 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.12Does Ford-Fulkerson always terminate?In case of irrational capacities,not necessarily!(Exercise)But we cant give irrational capacities as inputs to digital computers anyway.In case of floating point capacities,who knows?13Integrality Theorem(26.11)If a flow network has integer valued capacities,there is a maximum flow with an integer value on every edge.The Ford-Fulkerson method will yield such a maximum flow.The integrality theorem is often extremely important when“programming”and modeling using the max flow formalism.14Reduction:Maximum Matching!Max FlowWhat is the maximum cardinality matching in G?15 G16 GstAll capacities are 117Finding a balanced set of RepresentativesA city has clubs C1,C2,Cn and parties P1,P2,Pm.A citizen may be a member of several clubs but may only be a member of one party.A balanced city council must be formed by including exactly one member from each club and at most uk members from party Pk.(Ahuja,Application 6.2)1819Local search checklistDesign:How do we find the first feasible solution?Neighborhood design?Which neighbor to choose?Analysis:Partial correctness?(termination)correctness)Termination?Complexity?20Complexity of Ford-FulkersonWe have at most|f|improvement steps(iterations of the while-loop).Is this the best possible bound?21ComplexityWe have at most|f|improvement steps(iterations of the while-loop)and this bound cannot be improved for the general Ford-Fulkerson method.How fast can we implement a single improvement step?22ComplexityAssume|V|-1|E|.Otherwise the graph is not connected.Then,Ford-Fulkerson can be implemented to run in time at most O(|E|f|).Is this fast?23Polynomial time algorithmsDefintion:A polynomial time algorithm is an algorithm than runs in time polynomial in n,where n is the number of bits of the input.How we intend to encode the input influences if we have a polynomial algorithm or not.Usually,some“standard encoding”is implied.In this course:Polynomial Fast Exponential Slow24java MaxFlow?How to encode max flow instance?25java MaxFlow 6#0|16|13|0|0|0#0|0|10|12|0|0#0|4|0|0|14|0#0|0|9|0|0|20#0|0|0|7|0|4|#0|0|0|0|0|0How to encode max flow instance?26Complexity of Ford-FulkersonWith standard(decimal or binary)representation of integers,Ford-Fulkerson is an exponential time algorithm.27java MaxFlow 111111#|1111111111111111|1111111111111|#|1111111111|111111111111|#|1111|11111111111111|#|111111111|11111111111111111111#|1111111|1111#|28Complexity of Ford-FulkersonWith unary(4 1111)representation of integers,Ford-Fulkerson is a polynomial time algorithm.Intuition:When the input is longer it is easier to be polynomial time as a function of the input length.An algorithm which is polynomial if integer inputs are represented in unary is called a pseudo-polynomial algorithm.Intuitively,a pseudo-polynomial algorithm is an algorithm which is fast if all numbers in the input are small.29Edmonds-Karp Edmonds-Karp algorithm for Max Flow:Implement Ford-Fulkerson by always choosing the shortest possible augmenting path,i.e.,the one with fewest possible edges.30Complexity of Edmonds-KarpEach iteration of the while loop can still be done in time O(|E|).The number of iterations are now at most O(|V|E|)regardless of capacities to be seen next.Thus,the total running time is O(|V|E|2)and Edmonds-Karp is a polynomial time algorithm for Max Flow.31Why at most O(|V|E|)iterations?When executing Edmonds-Karp,the residual network Gf gradually changes(as f changes).This sequence of different residual networks Gf satisfies:Theorem(Lemma 26.8 and Theorem 26.9):1)The distance between s and t in Gf never decreases:After each iteration of the while-loop,it either increases or stays the same.2)The distance between s and t in Gf can stay the same for at most|E|iterations of the while-loop before increasing.As the distance between s and t can never be more than|V|-1 and it starts out as at least 1,it follows from the theorem that we have at most(|V|-2)|E|iterations.