6.6最大流问题

第六节最大流问题最大流最小割定理基本概念主要定理最大流算法算法步骤算法复杂性1.基本概念给定有向网络G=(N,A,C).cij表示弧(i,j)∈A的容量,G有一个发点s和一个收点t(s,t∈N).令xij=通过弧(i,j)的流量显然有0≤xij≤cij(6.6.1)另外，流x=(xij)要遵守点守恒规则，即+vi=s∑xij-∑xji=0i≠s,t(6.6.2)-vi=t可行流：满足(6.6.1)和守恒方程(6.6.2)的流，简称为(s,t)-流{jj基本概念续设P是G中从s到t的无向路，则P的前向弧(i,j)是指其方向从s到t的弧；否则称为P的后向弧流x=(xij)的增广路P：P的每个前向弧(i,j)有xijcij,而P的每个后向弧(i,j)有xij0(s,t)-割：弧割(S,T)，其中s∈S，t∈T割(S,T)的容量：C(S,T)=∑∑cijv∑∑cij=C(S,T)(6.6.5)i∈Sj∈Ti∈Sj∈T2.主要定理定理6.6.1(增广路定理)一个可行流是最大流当且仅当不存在关于它的从s到t的增广路。定理6.6.2(整流定理)如果网络中所有弧容量是整数,则存在值为整数的最大流。定理6.6.3(最大流最小割定理)一个(s,t)-流的最大值等于(s,t)-割的最小容量。证明证明提示定理6.6.3(最大流最小割定理)一个(s,t)-流的最大值等于(s,t)-割的最小容量。提示由定理6.6.1的证明和(6.6.5)知该定理成立。定理6.6.2(整流定理)如果网络中所有弧容量是整数,则存在值为整数的最大流。证明设所有的弧容量都是整数，并令xij0=0，对所有i和j如果x0=(xij0)不是最大的，则由定理6.6.1知，存在关于x0的从s到t的增广路,即x0允许增广,因此它有一个整流x'=(xij'),它的值超过x0的值。如果x'还不是最大的,它又是允许增广的，用这个方法得到的每个可行流至少超过它前面的可行流一个整数单位,最后达到一个不允许增广的可行流,就是最大的.定理6.6.1(增广路定理)一个可行流是最大流当且仅当不存在关于它的从s到t的增广路.证明:必要性显然,因为若存在增广路,流就不是最大的.充分性设x是一个不存在关于它的从s到t的增广路的流,并设S是包含s的点集,使得对任意j∈S存在从s到j的增广路,且对任意j∈N-S不存在从s到j的增广路。令T是S的补集,由定义可知,对任意i∈S和j∈T,有xij=cij，xji=0由(6.6.4)得v=∑∑ciji∈Sj∈T即流的值等于割(S,T)容量。从(6.6.5)知x最大。3.最大流算法的步骤第1步(开始)令x=(xij)是任意可行流,可能是零流,给s一个永久标号(-,∞).第2步(找增广路)(2.1)如果所有标号都已经被检查，转到第4步。(2.2)找一个标号但未检查的点i,并做如下检查,对每一个弧(i,j),如果xij≤cij且j未标号,则给j一个标号(+i,δ(j)),其中δ(j)=min{cij-xij,δ(i)}；对每一个弧(j,i),如果xij0且j未标号,则给j一个标号(-i,δ(j)),其中δ(j)=min{xji,δ(i)}。(2.3)如果t已被标号,转到第3步;否则,转到(2.1).最大流算法的步骤续第3步(增广)由点t开始,试用指示标号构造一个增广路,指示标号的正负则表示通过增加还是减少弧流量来增大流值.抹去s点以外的所有标号,转到第2步。第4步(构造最小割)这时现行流是最大的,若把所有标号点的集合记为S,所有未标号点的集合记为T,便得到最小容量割(S,T),计算完成.例求解下图所示有向网络中自点1到点6的最大流。其中每条弧上的数表示其容量。1653428695625378最大流算法的复杂性设弧数为m，每找一条增广路最多需要进行2m次弧检查。如果所有弧容量都是整数，则最多需要v次增广，其中v是最大流值。所以，总的计算量为O(mv)。注：此算法的时间复杂性与最大流值v有关，所以说它并不是一个好的算法。如果大家感兴趣，可以查阅相关书籍，有好的算法，如复杂性为O(n3)的算法。