1 清华大学软件学院宋斌恒1 第九讲. Maximum Flow 极大流 清华大学 宋斌恒 清华大学软件学院宋斌恒2 流网实例 1.例1：管道中的流体 2.例2：电网中的电流 3.例3：通信网络中的信息流 4.例4：装配线上的零件流 清华大学软件学院宋斌恒3 概念 1.有向边：传输物质的管道 2.容量：每条管道有静态容量：单位时间 内可以通过物质的最大数量，如每天可 以通过100万立方米的石油管道 3.点：管道连接点，满足流量守恒律 清华大学软件学院宋斌恒4 1 3 2 4 s t 清华大学软件学院宋斌恒5 Kirchhoff’s电流定律 1.流量守恒定律： 1.流入同一节点的总流量等于流出同一节点总 流量 2.对于电流就是Kirchhoff’s定律 3.极大流问题：计算流网中满足约束（上 述守恒律）的从源到汇的最大流量。 清华大学软件学院宋斌恒6 流网的定义 1.流网G=(V,E)是一个具有非负边权的有向图， 边权c(u,v)叫做容量，如果(u,v)不属于E，我 们约定其容量c(u,v)＝0。 2.在流网上有两个特殊点源s和汇t。 3.对于每个点v，都有一条从s经过v到达t的路 径 2 清华大学软件学院宋斌恒7 续 4.流Flow：G上的一个流是一个实函数f： V×V?R, 它满足 1.容量约束：对所有u,v, f(u,v)≤c(u,v) 2.反对称：对所有u,v, f(u,v)＝－f(v,u) 3.流守恒：对所有u∈V-{s,t} ∑ v∈V f(u,v)=0 4.流f的值：|f| = ∑ v∈V f(s,v) 5. f(u,v)叫做从u到v的流，其值可正可负 清华大学软件学院宋斌恒8 极大流问题 1.给定流网G=(V,E)、流网上的容量c(u,v)，和源 s、汇t，求流f使得其流值取得极大 2.相关概念扩充 1.一个顶点v的总流入量：∑ u∈V，f(u,v)>0 f(u,v) 2.一个顶点v的总流出量：∑ u∈V，f(v,u)>0 f(v,u) 3.总净流量＝总流出量－总流入量 4.守恒律的另一种表述：在非源非汇点，总流出量 ＝总流入量 清华大学软件学院宋斌恒9 多源多汇问题 许多实际问题是多源多汇问题【见下页图】，也就 是说流网中有多个源，有多个汇，这样的问题如何 解决？ 我们通过添加人工源和汇的方法将多源多汇问题转 化为单源单汇的标准问题：【见下下页图】 1.添加人工源s和人工汇t两个节点， 2.添加s到原问题所有源对应的顶点的有向边，并赋予 ∞权， 3.添加原问题所有汇对应顶点到t到有向边，并赋予∞ 权， 4.于是原问题就变成了标准单源单汇问题。Why equivalent？ 清华大学软件学院宋斌恒10 s2 t1 t2 t3 s1 s3 s4 s5 清华大学软件学院宋斌恒11 s2 t1 t2 t3 s1 s3 s4 s5 s t 清华大学软件学院宋斌恒12 流的运算 设f是流函数，X和Y是V[G]的子集， 定义：f(X,Y)=∑ x∈X, y∈Y f(x,y) 那么我们有： 1.守恒律：对任意u属于V-{s,t}有f(u,V)=0【如何 证？】 2. f(s,V-s)=f(s,V) 3. f(X,X)=0 4. f(X,Y)=-f(Y,X) 5.如果X∩Y=φ，我们有： 1. f(X,Z)+f(Y,Z)=f(X ∪Y, Z) 2. f(Z,X)+f(Z,Y)=f(Z,X ∪Y) 3 清华大学软件学院宋斌恒13 流的值 |f| = f(s,V) = f(V,V)-f(V-s,V) = f(V,V-s) = f(V,t)+f(V,V-s-t) = f(V,t) 课堂练习： 如果(u,v)和(v,u)都不属于E，利用定义证明 f(u,v)=f(v,u)=0 清华大学软件学院宋斌恒14 Residual networks Definition of residual networks Let f be a flow in G, a residual network induced by f is a flow network G f =(V, E f ), such that ?C f (u,v)=c(u,v)-f(u,v) ?E f ={(u,v): C f (u,v)>0} We call (u,v) in E f is the residual edge and C f is the residual capacity 清华大学软件学院宋斌恒15 Compute a residual network from a flow network and a flow f 1 3 2 4 s t 清华大学软件学院宋斌恒16 1 3 2 4 s t 清华大学软件学院宋斌恒17 1 3 2 4 s t 清华大学软件学院宋斌恒18 1 3 2 4 s t 4 清华大学软件学院宋斌恒19 1 3 2 4 s t 清华大学软件学院宋斌恒20 Lemma 26.2 Let G=(V,E) be a flow network with source s and sink t, and f be a flow in G. Let G f be the residual network of G induced(诱导) by f. Let f’ be a flow in G f , then f+f’ is a flow in G with |f+f’|=|f|+|f’| 清华大学软件学院宋斌恒21 Proof. Skew symmetry Capacity constrain Value of f+f’ 清华大学软件学院宋斌恒22 Augmenting paths(增广路径) Given a flow network G=(V,E) and a flow f, an augmenting path p is a simple path from s to t. Residual capacity of an augmenting path p is given by c f (p)=min{c f (u,v): (u,v) is on p} 清华大学软件学院宋斌恒23 Flow f p induced by p The following function f p : is a flow in G f . other wise p on is u)(v, If p on is v)(u, If 0 )( )( ),( ? ? ? ? ? ?= pc pc vuf f f p 清华大学软件学院宋斌恒24 f+f p is a flow in G and its value is greater than f. | f+f p |=| f |+| f p |>| f| 5 清华大学软件学院宋斌恒25 Cuts of flow networks ?S T? 1 2 3 4 s t 清华大学软件学院宋斌恒26 Cut A cut (S,T) divides the flow G=(E,V) into two parts S and T, where S ∩T=φ, and S∪T=E, s∈S, t∈T. Net flow across a cut (S,T) is defined to be f(S,T), the capacity of (S,T) is c(S,T) c(S,T)=∑ u ∈S,v ∈T c(u,v) f(S,T)=∑ u ∈S,v ∈T f(u,v) 清华大学软件学院宋斌恒27 Lemma 26.5 f(S,T)=|f| Proof: f(S,T) = f(S,V)-f(S,S) = f(S,V) = f(s,V)+f(S-s,V) = f(s,V) = |f| 清华大学软件学院宋斌恒28 Corollary 26.6 f(S,T)≤c(S,T) Notes: the definition of f and c. 清华大学软件学院宋斌恒29 Theorem 26.7(Max-flow min-cut theorem) If f is a flow in a flow network G=(V,E) with source s and sink t, then the following conditions are equivalent: 1.f is a maximum flow in G 2.The residual network G f contains no augmenting paths 3.|f|=c(S,T) for some cut (S,T) of G 清华大学软件学院宋斌恒30 Proof: (1)?(2): If there exists an augmenting path p in the residual network G f , then there is a induced flow f p on G f , hence there exists another flow f+f p on G such that its flow is bigger than f, which is a contradiction that f is a maximum flow on G. (2)?(3): Because G f contains no augmenting path, hence there are no path from s to t in G f . Let ?S={v∈V: there exists a path from s to v in G f } ?T=V-S Then the partition (S,T) is a cut, 6 清华大学软件学院宋斌恒31 (2)?(3) [continue] We claim that f(u,v)=c(u,v) for all u∈S and v∈T, if not, it implies that (u,v) ∈E f , which implies that v should be in S【矛盾！】, therefore, |f|=f(S,T)=c(S,T) (3)?(1): by corollary 26.6, |f|≤c(S,T) for all cuts (S,T), then the condition |f|=c(S,T) thus implies that f is a maximum flow. 清华大学软件学院宋斌恒32 The Basic Ford-Fulkerson algorithm Ford-Fulkerson(G,s,t) 1. For each edge (u,v) in E[G] 1. f[u,v]?0 2. f[v,u]?0 2. While there exists a path p from s to t in the residual network G f 1. c f (p)?min{c f (u,v): (u,v) in p} 2. For each edge (u,v) in p 1. f[u,v]?f[u,v]+ c f (p) 2. f[v,u]?- f[u,v] 清华大学软件学院宋斌恒33 Analysis of Ford-Fulkerson Initializing: O(E) Every augmenting: Find a path p on G f : O(E+V)=O(E) if using BFS or DFS compute c f (p): O(V) Augmenting f: O(V) ?How many steps of augmenting? If it is x then the total running time is O(Vx) 清华大学软件学院宋斌恒34 The estimation of x Case 1. If all of the capacity values are integer, then x≤f*, where f* is the maximum flow of the flow network. Proof: At every augmenting step the flow increases at least 1, hence x does not exceed f*. It can expand the case rational numbered capacity. Remark: computer can only treat rational number! 清华大学软件学院宋斌恒35 Explanation of Ford-Fulkerson’s Algorithm 清华大学软件学院宋斌恒36 1 3 2 4 s t 1 3 2 4 s t 找路径 改变流 7 清华大学软件学院宋斌恒37 1 3 2 4 s t 1 3 2 4 s t 清华大学软件学院宋斌恒38 1 3 2 4 s t 1 3 2 4 s t 清华大学软件学院宋斌恒39 1 3 2 4 s t 1 3 2 4 s t 清华大学软件学院宋斌恒40 1 3 2 4 s t 没有任何从s到t的路径 清华大学软件学院宋斌恒41 The following pictures show the bad cases for the Ford-Fulkerson’s method 清华大学软件学院宋斌恒42 u v s t 8 清华大学软件学院宋斌恒43 u v s t 清华大学软件学院宋斌恒44 u v s t 清华大学软件学院宋斌恒45 Edmonds-Karp algorithm If we use the BFS as the method to find an augmenting path, then such an implementing of Ford-Fulkerson Method call Edmonds-Karp algorithm. The kernel of Edmonds-Karp algorithm is that it can prove that x=O(EV) 清华大学软件学院宋斌恒46 Proof of x=O(EV) in Edmonds- Karp algorithm Step1: for all vertices v in V-{s,t}, the shortest-path distance δ f (s,v) in the residual network G f increases monotonically with each flow augmentation.【残网距离递增】 清华大学软件学院宋斌恒47 续 Step2: Every edge can become critical at most |V|/2-1 times; here above critical edge means it is in an augmenting path and its value equals the capacity of the path.【边为 关键边个数有限】 By step2, in Edmonds-Karp algorithm, it will complete in (|V|/2-1)*E steps of augmentations. 清华大学软件学院宋斌恒48 Proof of step1(Lemma 26.8) Suppose that there exists a flow f, a next augmented flow f’ and a vertex v’ in V-{s,t} not satisfies the property mentioned in step1, that is δ f (s,v’)≤δ f’ (s,v’) does not hold, then we choose v be one of such elements which takes the minimum distance from s in G f’ 【f’的残网】 【蓝字什么意思？为什么能这样假设？】 9 清华大学软件学院宋斌恒49 续 即 δ f (s,v)＞δ f’ (s,v) Let p=s--->u?v be a shortest path from s to v in G f’ , so that (u,v) in E f’ and δ f’ (s,u)＝δ f’ (s,v)-1 【三角不定式】and δ f’ (s,u)≥δ f (s,u), 【假设，】 清华大学软件学院宋斌恒50 We claim (u,v) not in E f . If it is, then δ f (s,v)≤δ f (s,u)+1 (triangle inequality) ≤δ f’ (s,u)+1 (see above，递增假设成立) ≤δ f’ (s,v) A contradiction! 续 清华大学软件学院宋斌恒51 续 How can we have (u,v) not in E f but in E f’ ? It is impossible! If it is true, then the augmentation must increased the flow from v to u. By the Edmonds-Karp algorithm always augment flow along the shortest paths, and the shortest path from s to u in G f has (v,u) as its last edge. Therefore, 清华大学软件学院宋斌恒52 δ f (s,v)= δ f (s,u)-1 ≤δ f’ (s,u)-1 【假设】 ≤δ f’ (s,v)-2 【三角不等式】 ≤δ f’ (s,v) Contradicts to δ f’ (s,v) < δ f (s,v) Conclusion: The assumption is incorrect. 续 清华大学软件学院宋斌恒53 Proof of step2: (Theorem 26.9) The critical time for an edge cannot exceed |V|/2-1. If (u,v) is critical at flow f and is not critical until to the flow f’, then we have δ f’ (s,u) = δ f’ (s,v)+1【临界假设】 ≥δ f (s,v)+1【递增性质】 = δ f (s,u)+2【临界假设】 Because the distance must be less than |V|-1, we have the critical time should be less than |V|/2-1. 清华大学软件学院宋斌恒54 Maximum Bipartite Matching 匹配的概念: Given an undirected graph G=(V,E), a matching is a subset M of edges in E such that for all vertices v in V, at most one edge of M is incident on v. If one edge is incident on v, we say v is matched by matching M, otherwise we say v is unmatched. A maximum matching is a matching such that it takes the maximum cardinality. 10 清华大学软件学院宋斌恒55 Bipartite graph A bipartite graph is a graph can be partitioned its vertices into two parts L and R, L and R are disjoined and all edges go between L and R 左L 右R 清华大学软件学院宋斌恒56 举例说明 二分图实例 清华大学软件学院宋斌恒57 Finding the maximum matching in a bipartite graph Is the maximum-bipartite-matching problem. Application of the matching problem: If L is set of machines, R is a set of tasks, the edges means that the machine can do the task. Finding the maximum simultaneously performing tasks 清华大学软件学院宋斌恒58 Convert the maximum-bipartite- matching problem to a maximum flow problem 左L 右R s t ？ 清华大学软件学院宋斌恒59 利用流求二分图的正确性 如何保证最后的最大流对应的边构成一 个匹配？ Ford－Fulkerson算法如何保证流是整 数？ 清华大学软件学院宋斌恒60 总结： 流的定义和属性 最大流与分割 残余流与增广路 Ford－Fulkerson方法 Ford－Fulkerson实现 Edmonds－Karp算法及其复杂性分析 最大流在最大二分匹配问题中的应用