信息学奥赛 网络流算法介绍与分析.ppt

信息学奥赛 网络流算法介绍与分析
第1页，共89页，2022年，5月20日，0点37分，星期一
一些符号和定义
V表示整个图中的所有结点的集合.
E表示整个图中所有边的集合.
G = (V,E) ,表示整个图.
s表示网络的源时，算法停止，此时的流就是最大流。
下面证明增广路算法的正确性.
第13页，共89页，2022年，5月20日，0点37分，星期一
将f,c,r的定义域扩展为点集
(在以后的叙述中,大写字母X,Y,S,T一般均表示点集)
点集间的流量和: f(X,Y) =
即:X中的任意一点与Y中的任意一点组成的所有边上的流量之和.(边的方向为从X中的结点到Y中的结点)
c,r等函数都有类似的定义.(点集间的容量和、点集间的残量网络容量和)
第14页，共89页，2022年，5月20日，0点37分，星期一
结论1
(X,X) = 0 (由流量反对称性)
2. f(X,Y) = -f(Y,X) (有流量反对称性)
(X ∪ Y,Z) = f(X,Z) + f(Y,Z) (显然)
(X,Y ∪ Z) = f(X,Y) + f(X,Z) (显然)
第15页，共89页，2022年，5月20日，0点37分，星期一
最大流最小割定理
网络流中这三个条件等价（在同一个时刻）:
1、f是最大流
2、残量网络中找不到增广路径
3、|f| = c(S,T)
第16页，共89页，2022年，5月20日，0点37分，星期一
1、f是最大流2、残量网络中找不到增广路径3、|f| = c(S,T)
1 -> 2证明: ,由于增广路径的容量至少为1,所以用这个增广路径增广过后的流的流量肯定要比f的大,这与f是最大流矛盾.
第17页，共89页，2022年，5月20日，0点37分，星期一
割的定义
一个割(S,T)由两个点集S,T组成.
S+T = V
s 属于 S.
t 属于 T.
提出割的定义,是为后面的证明作铺垫.
第18页，共89页，2022年，5月20日，0点37分，星期一
结论2(点集总流量为零)
不包含s和t的点集,于它相关联的边上的流量之和为0.
证明: f(X,V) =
= (由流量平衡)
= 0
第19页，共89页，2022年，5月20日，0点37分，星期一
结论3
任意割的流量等于整个网络的流量.
证明:
f(S,T) = f(S,V) – f(S,S) (由辅助定理1)
= f(S,V) (由辅助定理1)
= f(S,V) + f(S – s,V) (同上)
= f(s,V) (由辅助定理2)
= |f| (由|f|的定义)
第20页，共89页，2022年，5月20日，0点37分，星期一
结论4
网络的流量小于等于任意一个割的容量.()
即|f| <= c(S,T)
证明: |f| = f(S,T) = (由定义)
<= (由流量限制)
= c(S,T)
第21页，共89页，2022年，5月20日，0点37分，星期一
2 -> 3证明: 定义S = s ∪ {v | 在残量网络中s到v有一条路径} ; T = V- S. 则 (S,T) 是一个割.
|f| = f(S,T) (由辅助定理3)
而且,r(S,T) = 0. 假设不为0,则在残量网络中, 两个集合间必定有边相连,设在S的一端为v,在T的一端为u. 那么,s就可以通过v到达u,那么根据S的定义,.
所以,|f| = f(S,T) = c(S,T) – r(S,T) = c(S,T)
1、f是最大流2、残量网络中找不到增广路径3、|f| = c(S,T)
第22页，共89页，2022年，5月20日，0点37分，星期一
3 -> 1证明:
|f| <= c(S,T) (辅助定理4)
因为我们已经有|f| = c(S,T),如果最大流的流量是|f|+d (d>0),那么|f|+d肯定不能满足上面的条件.
1、f是最大流2、残量网络中找不到增广路径3、|f| = c(S,T)
第23页，共89页，2022年，5月20日