《算法课件Lecture13章节》由会员分享，可在线阅读，更多相关《算法课件Lecture13章节（25页珍藏版）》请在金锄头文库上搜索。
1、 2004 SDU,Maximum Flow Problem,Notions and definitions Ford and Fulkersons method Maximum matching in undirected bipartite graph, 2007 SDU 2,Maximum flow,Liquids flow through pipes Current through electrical networks Information through communication networks , 2007 SDU 3,Flow Networks,Definition: A
2、 flow network G=(V, E) is a directed graph together with a nonnegative map C: ER, called capacity, and two distinguished vertices s and t called the source (with no in-edges) and the sink (with no out-edges), respectively., 2007 SDU 4,Flow networks, 2007 SDU 5,Flow,A flow in a flow network G with so
3、urce s and sink t is a real-valued function f: ER 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, 2007 SDU 6,Value of a Flow,Call F the value of
4、 a flow f, where, 2007 SDU 7,Maximum-flow Problem,Input: a flow network G with source s and sink t Output: a flow of maximum value, 2007 SDU 8,Cut,Let S be a subset of V such that sS and tSC (SC =VS), (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
5、) 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?, 2007 SDU 9,Proof,For v V - s, t, Sum it for v SC - t Consider Add the above two, 2007 SDU 10,Proof,That is:, 2007 SDU 11,Capacity of A Cut,The capacity of a
6、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 suc
7、h that F=C(S), then F is maximum and (S,SC) is minimum cut respect to C(S)., 2007 SDU 12,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 from source s to si
8、nk t such that some additional flow can be pushed through the path The edges in the augmenting path may not have the same direction There are two kinds of edges in the augmenting path: Forward edge: Direction is the same with the path from s to t Backward edge: Direction is opposite to that of the p
9、ath from s to t, 2007 SDU 13,How to Determine an Augmenting Path?,Use a technique called label (forward and backward) process. Forward label: If an edge e = (u, v) satisfying u is labeled but v is not C(e) f(e) Label vertex v with vertex u Define (e) = C(e) f(e) Backward label: If an edge e = (u, v)
10、 satisfying v is labeled and u is not f(e) 0 Label vertex u with edge v Define (e) = f(e), 2007 SDU 14,The Ford-Fulkerson Method,Initialize the network with zero flow Repeat the following until no augmenting path exists Labeling s, using the forward and backward label procedure to find an augmenting
11、 path(e.g., by backtracking) Find the minimum (e), for each edge e on the path Update the flow according to the minimum If e is a forward edge, f(e) = f(e) + If e is a backward edge, f(e) = f(e) - Output the value of the flow f., 2007 SDU 15,An Example, 2007 SDU 16,An Example,According to Ford-Fulke
12、rson method，initial flow is zero-flow, 2007 SDU 17,An Example,Based on the current flow, we can find an augmenting path sabt，with 1=16. Revise the flow:,s,t,a,b,c,d,19:16,18:0,8:0,4:0,18:16,13:0,5:0,8:0,16:16,20:0,3:0, 2007 SDU 18,An Example,s,t,a,b,c,d,19:16,18:13,8:0,4:0,18:16,13:13,5:0,8:0,16:16,
13、20:13,3:0,2. Based on current flow, find an augmenting path scdt，with 2=13. Revise the flow:, 2007 SDU 19,An Example,s,t,a,b,c,d,19:16,18:16,8:0,4:0,18:16,13:13,5:0,8:3,16:16,20:16,3:3,3. Based on current flow, find an augmenting path scbdt，with 3=3. Revise the flow:, 2007 SDU 20,An Example,4. Based on current flow, find an augmenting path sabdt，with 4=2. Revise the flow:, 2007 SDU 21,An Example,5. Based on current flow, using the labeling rules, we can only label vertices s, a, c. No augmenting path exists. Algorithm
