最大流的入门笔记

比较重要的几点记录一下:

0.最大流可能不止一个。

1.在一个流网络中,流f=f(S,T)-f(T,S)。其中[S,T]是该流网络的任意一个割。

2.增广路经:残量网络中的一天简单路径

3.割的容量:割的容量不包括反向弧的容量

4.最大流最小割定理:

如果f是具有源s和汇t的网络G=(V,E,C)中的一个流,则下列条件是等价的:

(1)f是G的一个最大流;

(2)残留网络Gf不包含增广路经;

(3)对G的某个割[S,T],有|f|=c(S,T)。

可见,最大流的流量就是最小割的容量

5.Ford–Fulkson方法的基本思想

步骤:

(1)初始化网络中所有边的容量,c<u,v>继承该边的容量,c<v,u>初始化为0,边<v,u>就是回退边。初始化最大流流量flow=0.

(2)在残量网络中找一条从s到t的增广路p。找到则转步骤(3),否则转步骤(5)。

(3)在增广路p中找到所谓的“瓶颈”边,即路径中容量最小的边,记录下这个值X,并且累加到最大流中。

(4)将增广路中所有c<u,v>减去X,所有c<v,u>加上X,构成新的残留网络。转步骤(2)。

(5)得到最大流。退出。

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>