最大流

最大流问题的概念所谓最大流问题就是在一定的条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题，在最大流问题中一般有如下规定：①网络有一个起点υs和一个终点υt②网络是有向网络，即流有方向性。③在网络各条弧上都有一个权，表示允许流过的最大流量。若以bij表示由υi到υj的弧上允许流过的最大流量，以xij表示实际流过该弧的流量，则0≤xij≤bij④网络中，除起点υs和终点υt之外的任何顶点，流入量总和应该等于流出量的总和。最大流问题的数学模型最大流问题的数学模型：ijijjijjjibxtiftsisifxxtsf0,0.maxvs101165473915vtv5v3v4v2最大流最小割集定理1网络中的最大流量fmax值大小是由网络中最狭窄处瓶颈的容量所决定的。最大流－最小割集定理揭示了最小割集（网络中的瓶颈）容量与最大流量的关系，也提供了一个求最大流的方法。割集VSSSSCijjib),(},),({SSCjiji网络割集容量最小割集所有割集中容量最小的一个割集。最大流最小割集定理2网络中的最大流量fmax值大小是由网络中最狭窄处瓶颈的容量所决定的。VSSSSCijjib),(},),({SSCjiji网络割集容量最小割集所有割集中容量最小的一个割集。最大流－最小割集定理流过网络的最大流量等于最小割集的容量。最大流最小割集定理3vs101165473915vtv5v3v4v2SS割集容量vsv2v3v4v5vt(vsv2)(vsv3)24vsv2v3v4v5vt(vsv3)(v2v4)(v2v5)20vsv3v2v4v5vt(vsv2)(v3v2)(v3v4)(v3v5)29………..…福德－富克逊方法原理算法的原理首先，依据最大流问题的要求，为网络分配一个可行流。所谓可行流，是指所有弧上流量满足容量限制，所有中间点满足平衡条件的流；若这一可行流的流量就是最大流量，则问题已经解决；若不是最大流量，则增加流量获得流量更大的可行流。福德－富克逊方法流图求一个初始可行流是判断初始可行流是否最优结束不是求使目标得到改善的可行流福德－富克逊方法图示算法原理图示初始流初始流福德－富克逊方法讨论若弧(vi,vj)上的流量满足xij=bij，则称该弧为饱和弧，否则称为非饱和弧。若弧(vi,vj)上的流量xij=0。则称该弧为零流弧，否则称为非零流弧。一条从υs到υt的初等链是由υs开始的点、边序列，其中没有相同的点，也不考虑弧的方向。把这条链中的υs到υt方向相同的弧称为正向弧。把这条链中的υs到υt方向相反的弧称为逆向弧。在上述的可行流中，从υs到υt的某个初等链满足：①其上的正向弧均为非饱和弧。②其上的逆向弧均为非零流弧。则称该链为一条流量增广链。福德－富克逊方法讨论流量增广链:从υs到υt的某个初等链满足①其上的正向弧均为非饱和弧。②其上的逆向弧均为非零流弧。结论：若在可行流中，存在从υs到υt的增广链，则该可行流不是最大流，其流量可以增加；否则若不存在从υs到υt的增广链，则该可行流是最大流。增广链的性质流量增广链:从υs到υt的某个初等链满足①其上的正向弧均为非饱和弧。②其上的逆向弧均为非零流弧。增广链的性质：1Vs到增广链上任一点也有增广链;2增广链上任一点到Vt也有增广链;福德－富克逊方法步骤算法的步骤：①为网络分配初始流xij标在图中弧旁的()内②寻求增广链，若不存在，则已最优,否则③在增广链上调整流量，产生新的可行流。重复②、③两步，直到最优。寻求增广链的方法寻求流量增广链的方法，是依据增广链的性质而产生的，其基本思路类似于最短树问题的生长法。从υs开始，逐个检查每个点υi，看是否存在从υs到υi的增广链。如果存在从υs到υi的增广链，而（ViVj）非饱和或（VjVi）非零流，则存在从V1到Vj的增广链。福德－富克逊方法示例标记化算法的步骤：①为网络分配初始流xij标在图中弧旁的()内vs101156473915vtv5v3v4v2(4)(9)(3)(1)(5)(7)(5)(8)福德－富克逊方法示例②寻求增广链从υs开始，赋上标记（－，∞），表示υs是源点，能够得到任意多的量。υs称为已标记的点。也表示增广链可以从V1延伸到V1vs101156473915vtv5v3v4v2(4)(9)(3)(1)(5)(7)(5)(8)[-,∞]福德－富克逊方法示例②寻求增广链如果vi是已经标记的点,vj是未标记的点则当(vi,vj)是非饱和弧时,vj可以标记:[vi+,ej]ej=min{ei,bij-xij}当(vj,vi)是非零流弧时,vj可以标记:[vi-,ej]ej=min{ei,xji}如果vt可以标记,则找到增广链,否则继续.如果对于一切未标记的点,均不能再标记,则已经是最优.福德－富克逊方法示例②寻求增广链如图v1是已经标记的点,其它点是未标记的点(v1,v2)是非饱和弧,v2可以标记:[v1+,e2]e2=min{e1,b12-x12}(v1,v3)是饱和弧,目前v3和其它点暂时不能标记，即暂时没有从v1到v3或其它点的增广链。vs101156473915vtv5v3v4v2(4)(9)(3)(1)(5)(7)(5)(8)[-,∞][vs+,11]福德－富克逊方法示例②寻求增广链如图v2是已经标记的点,v3是未标记的点(v3,v2)是非零流弧,v3可以标记:[v2-,e3]e3=min{e2,x32}=min{11,3}[-,∞][vs+,11][v2-,3][v2+,4][v3+,3][v5+,4]vs1154315vtv5v3v4v2(4)(9)(1)(5)(7)(5)(8)1079(3)6福德－富克逊方法示例③在增广链上调整流量。vt已经标记,找到流量增广链。vs101156473915vtv5v3v4v2(4)(9)(3)(1)(5)(7)(5)(8)[-,∞][vs+,11][v2-,3][v2+,4][v3+,3][v5+,4]正向流流量增加et，逆向流流量减少et调整后流量f=17福德－富克逊方法示例②寻求增广链vs101154315vtv5v3v4v2(8)(9)(3)(1)(5)(7)(9)(8)(4)967[-,∞][vs+,7][v2-,3][v3+,1][v3+,3][v4+,3]vt已经标记,找到流量增广链。福德－富克逊方法示例③在增广链上调整流量。正向流流量增加et=3，逆向流流量减少et调整后流量f=20vs101154315vtv5v3v4v2(11)(9)(4)(5)(7)(9)(11)(4)967福德－富克逊方法示例②寻求增广链Vsv2已经标记，其余点不能标记，已经最优最大流量fmax=20vs101154315vtv5v3v4v2(11)(9)(4)(5)(7)(9)(11)(4)967[-,∞][vs+,4]