最大流算法及其应用

本文介绍了一种特殊的图——流网络及其相关问题,主要介绍的是最大流问题和最小割问题,并提出了解决方案。最后介绍了一些网络流相关的建模问题。

最大流算法及其应用

南京外国语学校 贾志鹏

【关键词】网络流、最大流问题、最小割问题

【摘要】本文介绍了一种特殊的图——流网络及其相关问题，主要介绍的是最大流问题和最小割问题，并提出了解决方案。最后介绍了一些网络流相关的建模问题。 【目录】

一、网络流相关的一些概念

（1）流网络 （2）流 （3）割

（4）残留网络 （5）增广路径 （6）增广

二、最大流和最小割问题

（1）最大流问题 （2）最小割问题 （3）最大流算法

三、最大流算法的应用

（1）最大流模型 （2）最小割模型

四、总结

本文介绍了一种特殊的图——流网络及其相关问题,主要介绍的是最大流问题和最小割问题,并提出了解决方案。最后介绍了一些网络流相关的建模问题。

一、网络流相关的一些概念

1. 流网络 (Flow Network)

流网络G (V,E)是一个有向图，其中每条边(u,v) E均有一非负容量

c(u,v) 0。如果

uv E，则假定c(u,v) 0。流网络中有两个特别的顶点：

源点s和汇点t。

图1 一个流网络的例子（边上的数字表示该弧的容量）

2. 流 (Flow)

G的流是一个实值函数f，f(u,v)表示顶点u到顶点v的流，它可以为正，为零，也可以为负，且满足下列三个性质：

容量限制：对所有u,v V，要求f(u,v) c(u,v)。 反对称性：对所有u,v V，要求f(u,v) f(v,u)。 流守恒性：对所有u V {s,t}，要求 f(u,v) 0。

v V

整个流网络G的流量f f(s,v)或f f(u,t)。

v V

u V

3. 割 (Cut)

流网络G (V,E)的割(S,T)将V划分成S和T V S两部分，使得s S，

t T。定义割(S,T)的容量为c(S,T)，则：

本文介绍了一种特殊的图——流网络及其相关问题,主要介绍的是最大流问题和最小割问题,并提出了解决方案。最后介绍了一些网络流相关的建模问题。

c(S,T)

u S,v T

c(u,v)

图2 一个割的例子（边上的数字表示该弧的容量，割的容量即为2+2+1+6=11）

4. 残留网络 (Residual Network)

给定一个流网络G (V,E)和流f，由f压得的G的残留网络Gf (V,Ef)，定义cf(u,v)为残留网络Gf中边(u,v)的容量。如果弧(u,v) E或弧(v,u) E，则弧(u,v) Ef，且cf(u,v) c(u,v) f(u,v)。在下面的各种概念和方法中，我们只考虑残留网络中容量大于0的弧，但是编程时为了方便还是保留了。

5. 增广路径 (Augmenting Path)

对于残留网络Gf中的一条s-t路径p称其为增广路径，定义增广路径p的残留容量为p上弧容量的最小值。后面求最大流要用到增广路径这个概念。

6. 增广 (Augment)

对于残留网络Gf中的一条增广路径p，增广的意思就是对于每一条属于p的弧(u,v)，将f(u,v)增加p的残留容量，将f(v,u)减少p的残留容量。这样的话，新的流f仍然满足流的三条性质，并且原流网络的流量f增加了。一般来说，增广过后就会修改残留网络，易得对于每一条属于p的弧(u,v)，要将cf(u,v

)

本文介绍了一种特殊的图——流网络及其相关问题,主要介绍的是最大流问题和最小割问题,并提出了解决方案。最后介绍了一些网络流相关的建模问题。

减去p的残留容量，cf(v,u)加上p的残留容量。（程序实现基本都是通过直接修改残留网络来实现增广的）

二、最大流和最小割问题

1. 最大流问题

对于一个流网络G (V,E)，其流量f的最大值称为最大流，最大流问题就是求一个流网络的最大流。

增广路定理：当且仅当由当前的流f压得的残留网络Gf中不存在增广路径时，流f的流量f达到最大。（证明在此略去，可以参见相关书籍）

根据增广路定理，我们可以设计出最基本的求最大流的方法，一开始将流网络G (V,E)的流f置为零流，即对于(u,v) E时，f(u,v) 0。然后构建残留网络，寻找增广路径增广，再修改残留网络，重复此过程，直到无法找到增广路径。此方法（之所以不是算法，是因为实现方法很多）称为Ford-Fulkerson方法。

2. 最小割问题

最小割是指流网络中容量最小的割。

Ford-Fulkerson定理（最小割最大流定理）：在流网络中，最小割的容量等于最大流的流量。（证明也在此略去）

根据这个定理，我们就可以通过求流网络的最大流来得到最小割。

3. 最大流算法

前面所讲的只是求最大流的一种方法，但怎样高效地实现还是一个问题。 这个方法的最大问题就在于怎样快速地找到一条增广路径。当然我们可以用最基本的搜索（DFS或BFS），但是这种方法肯定不够高效，这时我们就需要更高效的算法。

本文将重点介绍一种高效且实用的最大流算法：SAP算法（最短增广路算法）。

最短增广路算法(Shortest Augmenting Path Algorithm)，即每次寻找包含弧的个数最少的增广路进行增广，可以证明，此算法最多只需要进行

E

次2

本文介绍了一种特殊的图——流网络及其相关问题,主要介绍的是最大流问题和最小割问题,并提出了解决方案。最后介绍了一些网络流相关的建模问题。

增广。并且引入距离标号的概念，可以在O()的时间里找到一条最短增广路。最终的时间复杂 …… 此处隐藏：6823字，全部文档内容请下载后查看。喜欢就下载吧 ……