算法课件Lecture13章节.pptVIP

Maximum Flow Problem Notions and definitions Ford and Fulkerson’s method Maximum matching in undirected bipartite graph Maximum flow Liquids flow through pipes Current through electrical networks Information through communication networks … … Flow Networks Definition: A flow network G=(V, E) is a directed graph together with a nonnegative map C: E?R, called capacity, and two distinguished vertices s and t called the source (with no in-edges) and the sink (with no out-edges), respectively. Flow networks Flow A flow in a flow network G with source s and sink t is a real-valued function f: E?R that satisfies the following properties: Capacity constraint: For all e ? E, 0 ? f(e) ? c(e) Flow conservation: For all v ?V-{s, t}, ?(v): the set of edges entering vertex v ?(v): the set of edges leaving vertex v Value of a Flow Call F the value of a flow f, where Maximum-flow Problem Input: a flow network G with source s and sink t Output: a flow of maximum value Cut Let S be a subset of V such that s?S and t?SC (SC =V\S), (S, SC) be the set of edges of (u, v) ? E with u ? S and v ? SC, and (SC, S) be the set of edges of (u, v) ? E with u ? SC and v ? S. Call (S, SC) ? (SC, S) the cut defined by S. The value of a flow can be determined by any cut, that is, How to prove it? Proof For v ?V - {s, t}, Sum it for v ?SC - {t} Consider Add the above two Proof Capacity of A Cut The capacity of a cut determined by S is The max-flow min-cut theorem: Suppose F is the value of any flow f, and S is any subset of V such that s ?S, t ?SC, then F ? C(S). Proof is easy. The theorem indicates that for any subset S of V, if s ?S, t ?SC, C(S) is an upper bound of F, the value of any flow. If there is a S such that F=C(S), then F is maximum and (S,SC) is minimum cut respect to C(S). The Ford-Fulkerson Method The idea: Repeatedly find an augmenting path and change the current flow according to the path until no such path could be found. An augmenting path is a simple ‘path’