资源描述：
《_最大流算法及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、最大流算法及其应用最大流算法及其应用南京外国语学校贾志鹏【关键词】网络流、最大流问题、最小割问题【摘要】本文介绍了一种特殊的图——流网络及其相关问题，主要介绍的是最大流问题和最小割问题，并提出了解决方案。最后介绍了一些网络流相关的建模问题。【目录】一、网络流相关的一些概念（1）流网络（2）流（3）割（4）残留网络（5）增广路径（6）增广二、最大流和最小割问题（1）最大流问题（2）最小割问题（3）最大流算法三、最大流算法的应用（1）最大流模型（2）最小割模型四、总结第1页共13页最大流算法及其应用一、网络流相关的一些概念1.流网络(FlowNetwork)流网络G(,)
2、VE是一个有向图，其中每条边(,)uvE均有一非负容量cuv(,)0。如果(,)uvE，则假定cuv(,)0。流网络中有两个特别的顶点：源点s和汇点t。213234st12546图1一个流网络的例子（边上的数字表示该弧的容量）2.流(Flow)G的流是一个实值函数f，fuv(,)表示顶点u到顶点v的流，它可以为正，为零，也可以为负，且满足下列三个性质：容量限制：对所有uvV,，要求fuv(,)cuv(,)。反对称性：对所有uvV,，要求fuv(,)fvu(,)。流守恒性：对所有uV{,}st，要求fuv(,)0。vV整个流网络G的流量ff
3、sv(,)或ffut(,)。vVuV3.割(Cut)流网络G(,)VE的割(,)ST将V划分成S和TVS两部分，使得sS，tT。定义割(,)ST的容量为cST(,)，则：第2页共13页最大流算法及其应用cST(,)cuv(,)uSvT,213234st12546图2一个割的例子（边上的数字表示该弧的容量，割的容量即为2+2+1+6=11）4.残留网络(ResidualNetwork)给定一个流网络G(,)VE和流f，由f压得的G的残留网络G(,VE)，ff定义cuv(,)为残留网络G中边(,)uv的容量。如果弧(,)uvE或弧(,)vu
4、E，则ff弧(,)uvE，且cuv(,)cuv(,)fuv(,)。在下面的各种概念和方法中，我们只ff考虑残留网络中容量大于0的弧，但是编程时为了方便还是保留了。5.增广路径(AugmentingPath)对于残留网络G中的一条s-t路径p称其为增广路径，定义增广路径p的残f留容量为p上弧容量的最小值。后面求最大流要用到增广路径这个概念。6.增广(Augment)对于残留网络G中的一条增广路径p，增广的意思就是对于每一条属于pf的弧(,)uv，将fuv(,)增加p的残留容量，将fvu(,)减少p的残留容量。这样的话，新的流f仍然满足流的三条性质，并且原流网络的流量
5、f增加了。一般来说，增广过后就会修改残留网络，易得对于每一条属于p的弧(,)uv，要将cuv(,)f第3页共13页最大流算法及其应用减去p的残留容量，cvu(,)加上p的残留容量。（程序实现基本都是通过直接修f改残留网络来实现增广的）二、最大流和最小割问题1.最大流问题对于一个流网络G(,)VE，其流量f的最大值称为最大流，最大流问题就是求一个流网络的最大流。增广路定理：当且仅当由当前的流f压得的残留网络G中不存在增广路径f时，流f的流量f达到最大。（证明在此略去，可以参见相关书籍）根据增广路定理，我们可以设计出最基本的求最大流的方法，一开始将流网络G(,)VE的流
6、f置为零流，即对于(,)uvE时，fuv(,)0。然后构建残留网络，寻找增广路径增广，再修改残留网络，重复此过程，直到无法找到增广路径。此方法（之所以不是算法，是因为实现方法很多）称为Ford-Fulkerson方法。伪代码如下：FORD-FULKERSON-METHORD(G,s,t)1initializeflowfto02whilethereexistsanaugmentingpathp3doaugmentflowfalongp4returnf2.最小割问题最小割是指流网络中容量最小的割。Ford-Fulkerson定理（最小割最大流定理）：在流网络中，最小割的
7、容量等于最大流的流量。（证明也在此略去）根据这个定理，我们就可以通过求流网络的最大流来得到最小割。3.最大流算法前面所讲的只是求最大流的一种方法，但怎样高效地实现还是一个问题。这个方法的最大问题就在于怎样快速地找到一条增广路径。当然我们可以用最基本的搜索（DFS或BFS），但是这种方法肯定不够高效，这时我们就需要更高效的算法。本文将重点介绍一种高效且实用的最大流算法：SAP算法（最短增广路算法）。最短增广路算法(ShortestAugmentingPathAlgorithm)，即每次寻找包VE含弧的个数最少的增广路进行增广，可以证明，此算
