运筹学 Operations Research §6.6最大流问题 在生产生活中有许多网络,如电网、供水网、原油管道 运输网、交通运输网、通讯网、国际互联网等.以供水网络 为例,设仅有一个出水口和一个进水口.网络每段管道都有 个容量(单位时间内通过管道的最大水量).水由出水口 流出经过水管网络后流入进水口,这就形成一个水的实际的 稳定的有向的流动,称之为流 显然,流具有如下性质: (1)每段管道中通过的流量不超过该管道的容量; (2)网络的每个内部顶点处的流入量等于与流出量; 3)出水口的总流出量等于进水口的流入量.因受自身 网络结构的限制,通过水管网络的流必有一个最大界限,称 之为最大流 2021/2/20
2021/2/20 1 运 筹 学 Operations Research 在生产生活中有许多网络，如电网、供水网、原油管道 运输网、交通运输网、通讯网、国际互联网等．以供水网络 为例，设仅有一个出水口和一个进水口．网络每段管道都有 一个容量（单位时间内通过管道的最大水量）．水由出水口 流出经过水管网络后流入进水口，这就形成一个水的实际的 稳定的有向的流动，称之为流． 显然，流具有如下性质： （1）每段管道中通过的流量不超过该管道的容量； （2）网络的每个内部顶点处的流入量等于与流出量； （3）出水口的总流出量等于进水口的流入量．因受自身 网络结构的限制，通过水管网络的流必有一个最大界限，称 之为最大流． §6.6 最大流问题
运筹学 Operations Research 网络( network) 有向图D=(,A) 丿=X∪∪Y,X∩Y=d; 弧a∈A有容量( capacity)c(a) 发点(源, source):X 收点(汇,snk):Y 中间点( int termediate):I 单发点单收点网络: 发点:S(只流出) 收点:t(只流入) 中间点:I=V\{(中转) 2021/2/20 2
2021/2/20 2 运 筹 学 Operations Research 网络（network）： ermediate I Y X a A capacity c a V X I Y X Y D V A (int ): ( sink ): ( source): ( ) ( ). ( , ): 中间点 收点 汇， 发点 源， 弧 有容量 ， ＝ ； 有向图 = = 单发点单收点网络： 发点：s（只流出） 收点：t（只流入） 中间点：I = V \ {s,t} （中转）
运筹学 Operations Research 弧的容量:cn=c(v,")=c(a) ViO- 割(cut):(S,S)={(v,v)∈A ∈.1.∈ 割是从s到t的必经之道(桥),而 割的容量则为桥的最大通过能力 S=V\S 2021/2/20 3
2021/2/20 3 运 筹 学 Operations Research 弧的容量： c c(v ,v ) c(a) ij = i j = 割（cut）： (S,S) {(v ,v ) A| v S,v S} = i j i j 割是从s到t的必经之道（桥），而 割的容量则为桥的最大通过能力
运筹学 Operations Research 割的容量:c(S,S)=∑c(v,y) (v,v)(S,S) 最小割( minimum cut):容量最小的割. SV,1 S (S,S)=sv2,v,t, v3t; c(S,S)=12 2021/2/20 4
2021/2/20 4 运 筹 学 Operations Research 割的容量： = ( , ) ( , ) ( , ) ( , ) v v S S i j i j c S S c v v 最小割（minimum cut）：容量最小的割. 如 ( , ) 12 ( , ) { , , } { , , } 2 1 3 1 3 = = = c S S S S sv v t v t S s v v
运筹学 Operations Research 弧的流量(fux):f=f(v,v)=f(a) 流(flow):f 符号: 对KA,令f(K)=∑f(a) a∈K f(v)=f(v\w)=∑f(v (v, "E(v,v) f(v)=f(\v,)=∑f(v,) (v,)∈(Vvv) 2021/2/20
2021/2/20 5 运 筹 学 Operations Research 弧的流量（flux）： f f (v ,v ) f (a) ij = i j = 流（flow）： f 符号： ( ) ( ). = a K 对K A，令f K f a + = = ( , ) ( , \{ }) ( ) ( , \{ }) ( , ) v v v V v j j f v f v V v f v v − = = ( , ) ( \{ }, ) ( ) ( \{ }, ) ( , ) v v V v v j j f v f V v v f v v
运筹学 Operations Research f(s)=f(s\s)=∑f(s,v (S,")∈(s,s) ()=f(V,1)=∑ (v,D)∈(t},t) 可行流( feasible flow): (1)va∈A,有0≤f(a)≤c(a) (2)f(s)=f(t);vv∈l,有f(s)=f(t) 流值( flow value):vakf)=f*(s)=f() 2021/2/20 6
2021/2/20 6 运 筹 学 Operations Research + = = ( , ) ( , \{ }) ( ) ( , \{ }) ( , ) s v s V s j j f s f s V s f s v − = = ( , ) ( \{ }, ) ( ) ( \{ }, ) ( , ) v t V t t j j f t f V t t f v t 可行流（feasible flow）： (1)a A，有0 f (a) c(a) (2) f (s) f (t) v I f (s) f (t) + − + − = ； ，有 = 流值（flow value）： val( f ) f (s) f (t) + − = =
运筹学 Operations Research 零流( zero flow):弧的流量都是0的流. 显然,零流是一个可行流,且流值为0 最大流( maximum flow):流值最大的可行流 最大流问题:在网络中找一个最大流 弧的分类: 1)按流量和容量的大小关系分: 饱和弧( saturated arc):f(a)=c(a) 不饱和弧( unsaturated arc):f(a)<c(a 2021/2/20 7
2021/2/20 7 运 筹 学 Operations Research 零流（zero flow）：弧的流量都是0的流. 显然，零流是一个可行流，且流值为0. 最大流（maximum flow）：流值最大的可行流. 最大流问题：在网络中找一个最大流. 弧的分类： （1）按流量和容量的大小关系分： 饱和弧（saturated arc）： 不饱和弧（unsaturated arc）： f (a) = c(a) f (a) c(a)
运筹学 Operations Research (2)按流量和0的大小关系分: 零弧( zero arc):f(a)=0 非零弧( nonzero arc, positive arc):f(a)>0 (3)按流量和有向路的关系分: 设是一条有向(s,t)-路,其方向为s→t 8o>0>0>≤0>t 前(正)向弧( forward arc):与P的方向一致的弧 后(反)向弧( forward arc):与P的方向相反的弧 2021/2/20 8
2021/2/20 8 运 筹 学 Operations Research （2）按流量和0的大小关系分： 零弧（zero arc）： 非零弧（nonzero arc，positive arc）： f (a) = 0 f (a) 0 （3）按流量和有向路的关系分： 设P是一条有向(s，t)-路，其方向为s→ t. 前（正）向弧（forward arc）：与P的方向一致的弧 后（反）向弧（forward arc）：与P的方向相反的弧
运筹学 Operations Research 可增广路( augmenting path):前向弧均为不饱和弧,后 向弧均为非零弧的路. Th1设是任一可行流,(S,S)是任一割,则 (1)val(O)≤c(S,S) (2)nal(f)=c(S,S)分(S,S)中的前向弧均为饱和弧, 后向弧均为零弧囗 Cor(1)若为最大流(S,S)为最小割,则vl()≤c(S,S) 2)最大流和最小割必存在 (3)若val(f)=c(S,S),则为最大流S,S)为最小割■ 2021/2/20
2021/2/20 9 运 筹 学 Operations Research 可增广路（augmenting path）：前向弧均为不饱和弧，后 向弧均为非零弧的路. . (2) ( ) ( , ) ( , ) (1) ( ) ( , ) 1 ( , ) 后向弧均为零弧 中的前向弧均为饱和弧， 设 是任一可行流， 是任一割，则 val f c S S S S val f c S S Th f S S = ▌ (3) ( ) ( , ) ( , ) . (2) . (1) ( , ) ( ) ( , ). 若 ，则 为最大流， 为最小割 最大流和最小割必存在 若 为最大流， 为最小割，则 val f c S S f S S Cor f S S val f c S S = ▌
运筹学 Operations Research Lemma设P是一条关于可行流/的可增广路,则可 利用P来改进 证:令 (P)=mint (v,)是P的前向弧(v,”)是P的后向弧 f+1(P),(v,v)是P的前向弧 G:=1f-(P)(,v)是P的后向弧 (V, V)EP 则f仍为可行流,且vl()=val)+l(P)>v/).■ 2021/2/20 10
2021/2/20 10 运 筹 学 Operations Research . emma1 P f L P f 利用 来改进 设 是一条关于可行流 的可增广路，则可 ) ( ) ( ) ( ). ˆ ( ˆ , ( , ) ( ), ( , ) ( ), ( , ) : ˆ f val f val f l P val f f v v P f l P v v P f l P v v P f i j i j i j i j i j i j i j = + − + = 则 仍为可行流，且 是 的后向弧 是 的前向弧 ( ) min{ , } ( , )是 的前向弧 ( , )是 的后向弧 证：令 v v P i j v v P i j i j i j i j l P = c − f f ▌