最大流算法及其应用.pptVIP

三、最大流算法的应用最大流模型一个典型的最大流模型就是二分图的最大二分匹配。二分图G=(X,Y,E)，其中X和Y是两个不相交的点集，并且对于每对(u,v)∈E，u∈X且v∈Y。二分图的最大二分匹配问题就是从E中选择一些边，使得每个点最多在选择的边里出现一次，问最多能选多少条边。图2一个二分图的例子及其最大匹配（实线表示选中的边，虚线表示未选中的边）分析实际上我们可以将二分图的最大匹配问题转换为最大流问题。增加源和汇，将源连到每个左边的点，将每个右边的点连到汇，并把原来的边改为有向的，从左边的点指向右边的点，最后把图中所有弧的容量赋为1，这个流网络的最大流即为原二分图的最大匹配。图3新建的流网络（图中弧的容量均为1）st最大流算法及其应用提要网络流相关的一些概念最大流和最小割问题最大流算法的应用总结一、网络流相关的一些概念流网络(FlowNetwork)流网络是一个有向图G=(V,E)，其中每条边(u,v)∈E均有一非负容量c(u,v)≥0。如果(u,v)∈E，则假定c(u,v)=0。流网络中有两个特别的顶点：源点s和汇点t。图1一个流网络的例子stv1v4v5v2v3v635221642314流(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∈V-{s,t}，要求流量整个流网络G的流量：割(Cut)流网络G=(V,E)的割(S,T)将划分成S和T=V-S两部分，使得s∈S，t∈T。定义割(S,T)的容量为c(S,T)，则：残留网络(ResidualNetwork)给定一个流网络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的弧，但是编程时为了方便还是保留了。增广路径(AugmentingPath)对于残留网络Gf中的一条s-t路径p称其为增广路径，定义增广路径p的残留容量为p上弧容量的最小值。后面求最大流要用到增广路径这个概念。增广(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的残留容量。（程序实现基本都是通过直接修改残留网络来实现增广的）二、最大流和最小割问题最大流问题对于一个流网络G=(V,E)，其流量|f|的最大值称为最大流，最大流问题就是求一个流网络的最大流。增广路定理当且仅当由当前的流f压得的残留网络Gf中不存在增广路径时，流f的流量|f|达到最大。（证明在此略去，可以参见相关书籍）根据增广路定理，我们可以设计出最基本的求最大流的方法，一开始将流网络G=(V,E)的流f置为零流，即对于(u,v)∈E时，f(u,v)=0。然后构建残留网络，寻找增广路径增广，再修改残留网络，重复此过程，直到无法找到增广路径。此方法（之所以不是算法，是因为实现方法很多）称为Ford-Fulkerson方法。Ford-Fulkerson方法的伪代码returnfdoaugmentflowfalongpwhilethereexistsanaugmentingpathpinitializeflowfto0FORD-FULKERSON-METHORD(G,s,t)最小割问题最小割是指流网络中容量最小的割。Ford-Fulkerson定理（最小割最大流定理）：在流网络中，最小割的容量等于最大流的流量。（证明也在此略去）根据这个定理，我们就可以通过求流网络的最大流来得到最小割。最大流算法前面所讲的只是求最大流的一种方法，但怎样高效地实现还是一个问题。这个方法的最大问题就在于怎样快速地找到一条增广路径。当然我们可以用最基本的有哪些信誉好的足球投注网站（DFS或BFS），但是这种方法肯定不够高效，这时我们就需要更高效的算法。本文将重点介绍一种高效且实用的最大流算法：SAP算法（最短增广路算法）。