流网实例 1.例1:管道中的流体 第九讲 Maximum flow 2.例2:电网中的电流 极大流 3.例3:通信网络中的信息流 4.例4:装配线上的零件流 清华大学 宋斌恒 清华大学就件学院末恒 请华大学轼件学院宋斌恒 概念 12/12 11/16 15/20 1.有向边:传输物质的管道 2.容量:每条管道有静态容量:单位时间 101/4/7 内可以通过物质的最大数量,如每天可 以通过100万立方米的石油管道 8/13 3.点:管道连接点,满足流量守恒律 清华大学软件学院宋恒 請华大学轼件学院宋斌包 流网的定义 Kirchhoffs电流定律 1.流网G=(VE)是一个具有非负边权的有向图 边权c(uV)叫做容量,如果(uv)不属于E,我 1.流量守恒定律: 们约定其容量c(uv)=0 流入同一节点的总流量等于流出同一节点总 2.在流网上有两个特殊点源s和汇t 流量 2.对于电流就是 Kirchhoffs定律 3.对于每个点v,都有一条从s经过v到达t的路 3.极大流问题:计算流网中满足约束(上 述守恒律)的从源到汇的最大流量 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒
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的路 径
极大流问题 续 1.给定流网G=(VE)、流网上的容量c(uv),和源 s、汇t,求流使得其流值取得极大 4.流Flow:G上的一个流是一个实函数f: 2.相关概念扩充 V×V→R,它满足 1.容量约束:对所有u,v,f(u,v)≤cuy) 1.一个顶点v的总流入量:∑uev, fuvpofqu,v) 2.一个顶点v的总流出量:Euev, fly.upof(v,u) 2.反对称:对所有uw,f(uy)=-fv,u) 3.总净流量=总流出量一总流入量 3.流守恒:对所有u∈V-{st}∑vevf(uv)=0 4守恒律的另一种表述:在非源非汇点,总流出量 4.流的值:1=∑、evfv 总流入量 f(u,v)叫做从u到v的流,其值可正可负 清华大学就件学院末恒 请华大学轼件学院宋斌恒 多源多汇问题 多实际问题是多源 题【见下页图】,也就 是说流网中有多个源,有多个汇,这样的问题如何 16 解决? 灯单加的标灌题的徒多丁间题转 1.添加人工源s和人工汇t两个节点, 2.添加s到原问题所有源对应的顶点的有向边,并赋予 3.添加原问题所有汇对应顶点到t到有向边,并赋予∞ 4.于是原问题就变成了标准单源单汇问题。Why equivalent? 清华大学软件学院宋恒 (a)件学院来 流的运算 设f是流函数,X和Y是Ⅴ[G]的子集 定义:f(X,Y)=∑ 我们有 1.守恒律:对任意u属于V-{s,t有f(uV=0【如何 2. f(s, v-sFf( 3.fx,x)=0 4. f(X, Y-f(Y, X) 5.如果X∩Y=φ,我们有 清华大学 (6 2.t2,x+1zY=从学段宋玻如
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∈Vf(u,v)=0 4. 流f的值：|f| = ∑v∈Vf(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)>0f(u,v) 2.一个顶点v的总流出量： ∑u∈V，f(v,u)>0f(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)
流的值 Residual networks s Definition of residual networks aLet f be a flow in G. a residual network induce f(V, V-s by f is a flow network G =(V, ED, such that f(v, t)+f(V, V-S-t) Cdu,vc(u, vhf(u, v) f(V,t) (u, v)in Er is the residual 如果(u,v)和(v,u)都不属于E,利用定义证明 the residual capacity f(u, vFf(v, uFO 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Compute a residual network from a flow network and a flow f 12/12 11/16 15/20 12/12 15/20 101/4/7 0/101/4 8/13 4/4 l/14 清华大学软件学院宋恒 請华大学轼件学院宋斌包 12/12 1/4 12/13 南华大学软件学院宋就恒 请华大学软件学院宋斌智
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 Gf =(V, Ef ), such that • Cf (u,v)=c(u,v)-f(u,v) • Ef ={(u,v): Cf (u,v)>0} We call (u,v) in Ef is the residual edge and Cf 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
Lemma 26.2 s Let g=(v,E)be a flow network with source 113 sink t, and f be a flow in G. Let Gr be the residual network of g induced(诱导)by f Let f be a flow in g. then f+f is a fl in g with fIfI+IfI 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Augmenting paths(增广路径) 素 Skew symmetry a Given a flow network G=(V,E)and a flow f s Capacity constrain an augmenting path p is a simple path from 成 Value of f+f s to t m Residual capacity of an augmenting path p cdu,v): (u, v) is on pi 清华大学软件学院宋恒 請华大学轼件学院宋斌包 low f, induced by p is a flow in g and its value ater than f sThe following function fp 什fHfF (p) If (u, v)is on p fp(u,v)=-c,(p)If(v, u)is onp 0 other wise 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒
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 Gf be the residual network of G induced(诱导) by f. Let f’ be a flow in Gf , 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 cf (p)=min{cf (u,v): (u,v) is on p} 清华大学 软件学院 宋斌恒 23 Flow fp induced by p The following function fp: is a flow in Gf . other wise If (v,u) is on p If (u, v) is on p 0 ( ) ( ) ( , ) ⎪ ⎩ ⎪ ⎨ ⎧ = − c p c p f u v f f p 清华大学 软件学院 宋斌恒 24 f+fp is a flow in G and its value is greater than f. | f+fp |=| f |+| fp |>| f|
Cuts of flow networks Cut sA cut(S, T)divides the flow G=(E, V) into 1116 15/20 two parts S and T, where S nT=o, and S∪T=E,s∈S,t∈T 4 1/4 7/7 A Net flow across a cut(s, T) is defined to be f(s, T), the capacity of(S, T)is c(S, 票c(S,T=∑u∈sy∈rc(uv) 1I14 病f(S,D=∑u∈ Svet f(uv) 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Lemma 26.5 Corollary 26.6 素f(S,T= f(S,D≤c(S,T af(S,T)=f(S,v)r-f(s, S) s Notes the definition of f and c f(s,V f(s, V)+(S-S,V) 清华大学软件学院宋恒 請华大学轼件学院宋斌包 Theorem 26.7(Max-flow min-cut 赛 Proof M1)e(2): If there exists an augmenting path p in theorem) the residual network G, then there is a induced sIf f is a flow in a flow network G=(V, E) flow f on g. hence there exists another flow f+f source s and sink t, then the following on G such that its flow is bigger than f, which is a conditions are equivalent 2(2)2(3): Because Gr contains no augmenting path, 1.f is a maximum flow in g hence there are no path from s to t in ge. Let 2.The residual network Gr contains no 3.fFc(S, T) for some cut(S, T)of G >Then the partition(S,T)is a cut, 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒 5
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 ∈Tc(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 Gf 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 Gf , then there is a induced flow fp on Gf , hence there exists another flow f+fp 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 Gf contains no augmenting path, hence there are no path from s to t in Gf . Let • S={v∈V: there exists a path from s to v in Gf } • T=V-S Then the partition (S,T) is a cut
(2)73)continue bWe claim that f(u,v=c(u,v) for all u∈ S and v∈T, The Basic Ford-Fulkerson if not, it implies that(u, v)EE which implies that v should be in s【矛盾!】, therefore, >f=f(S,TFc(,T) s Ford-Fulkerson(G, s, t) 1. For each edge (u,v)in E[G P(3)(1): by corollary 26.6, fsc(s, T) for all cuts 1.uyvl←0 (S,T), then the condition f=c(s, T)thus implies 2. fv, u]e0 that f is a maximum flow While there exists a path p from s to t in the residual 1.cp)∈ mined, v):(u, v)in p} 2. For each edge(u, v)in p lu,v]e fu,vl+ cdp 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Analysis of Ford-Fulkerson The estimation of x s Initializing: O(E) Case 1. If all of the capacity values are integer Ev then xsf where f* is the maximum flow of X Find a path p on G: O(E+VO(E)if using BFS or des Proof: At every augmenting step the flow increases at least 1. hence x does not exceed f 2* compute cdp): O(V) a It can expand the case rational numbered 2* Augmenting f: OV) ?How many steps of augmenting? If it is x rk: computer can only treat rational hen the total running time is O(vx) 清华大学软件学院宋恒 請华大学轼件学院宋斌包 7 s Explanation of Ford-Fulkerson's Algorithm 找路径 4/ 4/4改变流 南华大学软件学院宋就恒 414院 6
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) ∈Ef , 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 Gf 1. cf (p)Åmin{cf (u,v): (u,v) in p} 2. For each edge (u,v) in p 1. f[u,v]Å f[u,v]+ cf (p) 2. f[v,u]Å - f[u,v] 清华大学 软件学院 宋斌恒 33 Analysis of Ford-Fulkerson Initializing: O(E) Every augmenting: Find a path p on Gf : O(E+V)=O(E) if using BFS or DFS compute cf (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 找路径 改变流
c 7 12/ 116 15/20 04 101/4 4/4 没有任何从s到t的路径 101/4 請华大学轼件学院宋斌包 <The following pictures show the bad cases for the ford-Fulkerson's method 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒
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
清华大学就件学院末恒 请华大学轼件学院宋斌恒 Edmonds-Karp algorithm Proof of x-O(EV) in Edmonds- Karp algorithm s If we use the bfs as the method to find an a Stepl: for all vertices v in V-is, t), the augmenting path, then such an shortest-path distance 8(s, v)in th implementing of Ford-Fulkerson Method residual network Gr increases call Edmonds-Karp algorithm monotonically with each flow sThe kernel of Edmonds-Karp algorithm is augmentation.【残网距离递增】 that it can prove that 清华大学软件学院宋恒 請华大学轼件学院宋斌包 续 Proof of stepl( Lemma 26.8) s Suppose that there exists a flow f, a next <Step2: Every edge can become critical at augmented flow f and a vertex v'in V-is, t) I times: here above critical edge not satisfies the property mentioned in stepl means it is in an augmenting path and its that is 8(s, v)<8(s, v)does not hold value equals the capacity of the path.【边为 s then we choose y be one of such elements 关键边个数有限】 which takes the minimum distance from s in s By step2, in Edmonds-Karp algorithm, it G,【f的残网】 will complete in(vp2-1)*E steps of 【蓝字什么意思?为什么能这样假设?】 augmentation 华大学软件字院宋 请华大学狱件学院宋斌恒 8
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 EdmondsKarp algorithm Step1: for all vertices v in V-{s,t}, the shortest-path distance δf (s,v) in the residual network Gf 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 Gf’ 【f’的残网】 【蓝字什么意思？为什么能这样假设？】
续 续 s We claim(u, v)not in Et 6s,V)>8(,V) >m If it is, then a Gr, So that(u,v)in Er andh froms to v et p=s-->u>v be a shortest 8(s, v)8(s, u)+1(triangle inequality) 6-(S,u)=6(SV1【三角不定式】and ≤6(s,u)+l( see above,递增假设成 61(s,u)≥8(s,u),【假设,】 ≤8(V) 清华大学就件学院末恒 请华大学轼件学院宋斌恒 续 续 How can we have(u, v) not in E but in Er? sIt is impossible! If it is true, then the ≤64(S,u}1【假设】 augmentation must increased the flow from ≤64(SV2【三角不等式】 v to u. By the Edmonds-Karp algorithm ≤8(SV) always augment flow along the shortest Contradicts to paths, and the shortest path from s to u in Ge 8(s,V)<8s,v) has(v, u)as its last edge. Therefore Conclusion: The assumption is incorrect. 清华大学软件学院宋恒 請华大学轼件学院宋斌包 Proof of step2: (Theorem 26.9) Maximum Bipartite Matching The critical time for an edge cannot exceed 匹配的概念: Ny2-1 Given an undirected graph G=(V,E), a matching If(u, v) al at flow f and is not critical until to the flow f. then we have is a subset m of edges in e such that for all vertices v in v. at most one edge of m is 8(su)=8(sV)+1【临界假设】 ≥8(sV+1【递增性质】 incident on v. If one edge is incident onv, we 6s,u)+2【临界假设】 say v is matched by matching M, otherwise we Because the distance must be less than /VIl,we say v is unmatched have the critical time should be less than v2-1 kimm matching is a ma such that it the maximum cardinali 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒
9 清华大学 软件学院 宋斌恒 49 续 即 δf (s,v)＞ δf’(s,v) Let p=s--->uÆv be a shortest path from s to v in Gf’ , so that (u,v) in Ef’ and δf’(s,u)＝δf’(s,v)-1 【三角不定式】and δf’(s,u)≥ δf (s,u), 【假设，】 清华大学 软件学院 宋斌恒 50 We claim (u,v) not in Ef . 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 Ef but in Ef’? 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 Gf 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
Bipartite grap 举例说明 a bipartite graph is a graph can be 赢二分图实例 ertices into two parts L and r, L and r are disjoined and all edges go between 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Finding the maximum matching Convert the maximum-bipartite in a bipartite graph atching problem to a maximum flow problem s Application of the matching problem lf L is set of machines R is a set of tasks the means that the machine can do the task ing the maximum simultaneously erforming tasks 清华大学软件学院宋恒 請华大学轼件学院宋斌包 利用流求二分图的正确性 总结: 燕如何保证最后的最大流对应的边构成 燕流的定义和属性 个匹配 最大流与分割 Ford- Fulkerson算法如何保证流是整 残余流与增广路 血Ford- Fulkerson方法 端Ford- Fulkerson实现 燕 Edmonds-Karp算法及其复杂性分析 最大流在最大二分匹配问题中的应用 清华大学软件字院宋斌 请华大学狱件学院宋斌恒
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-bipartitematching problem to a maximum flow problem 左L 右R s ？ t 清华大学 软件学院 宋斌恒 59 利用流求二分图的正确性 如何保证最后的最大流对应的边构成一 个匹配？ Ford－Fulkerson算法如何保证流是整 数？ 清华大学 软件学院 宋斌恒 60 总结： 流的定义和属性 最大流与分割 残余流与增广路 Ford－Fulkerson方法 Ford－Fulkerson实现 Edmonds－Karp算法及其复杂性分析 最大流在最大二分匹配问题中的应用