运筹学 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