网络最大流

nullnull 网络流 求网络最大流nullnull 网络与流 网络D＝(V,A,C) 设D是一个简单有向图(D=(V,A))。在V中指定了一个顶点，称为源点(记为Vs)和另一个顶点，称为汇点(记为Vt)，对于每一条弧(Vi，Vj)A，对应有一个Cij＞=0，称为弧的容量。通常我们就把这样的D叫做一个网络，记作D=(V,A,C)。null 网络流F 所谓网络上的流是指定义在弧集合A上的一个函数F＝{Fij}，并称Fij为弧(Vi,Vj)上的流量。null 函数F＝{Fij}（ 且 ）： F12=3, F13=2, F23=2, F24=0, F25=1, F34=2, F35=2, F54=0, F56=3, F46=2 nullV1V2V4V6V5V3222P1: V1 V3 V4 V6nullV1V2V4V6V5V3P2: V1 V2  V3 V5 V62222nullV1V2V4V6V5V3111P3: V1 V2  V5 V6nullV1V2V4V6V5V3P2: V1 V2  V3 V5 V61=12=22=22=22=22=22=2002+1=3P3: V1 V2  V5 V6P1: V1 V3 V4 V62=22+1=3nullnull可行流与最大流 可行流(可行流的流量V(F)) 满足下述条件的流F称为可行流： (1)容量限制条件： 对每一条弧(Vi，Vj) ∈ A，0<=Fij<=Cijnull (2)平衡条件： 对于中间点： 流出量＝流入量,即对每个i(i<>s,t)有 Vi的流出量 -Vi的流入量=0 对于源点S： Vs的流出量 -Vs的流入量=源点的净输出量 对于汇点T： Vt的流出量 -Vt的流入量=(-1)*汇点的净输入量null 若给一个可行流F＝(Fij) 饱和弧：网络中Fij =Cij的弧 非饱和弧：网络中Fij ＜ Cij的弧 非零流弧：网络中 Fij＞0 的弧 零流弧：网络中 Fij =0的弧null 若P是网络中联结源点Vs和汇点Vt的一条路，我们定义路的方向是从Vs到Vt，则路上的弧被分成两类： 一类是弧的方向与路的方向一致，叫做前向弧。前向弧的全体记为P+。另一类弧与路的方向相反，叫做后向弧。后向弧的全体记为P-。 如图，在路P＝{Vl,V3,V2,V4,V6}中 P+＝{(Vl,V3)，(V2,V4)，(V4,V6)} P -＝{(V3,V2)}null 在图G中，一个由不同的边组成的序列e1,e2,…,eg，如果ei是连接Vi-1与Vi(i＝1,2,…,g)的，我们就称这个序列为从V0到Vg的一条道路，数g称为路长，V0与Vg称为这条道路的两个端点，Vi(1<=i<=g-1)叫做道路的内点。 对于 且 是边吗？null 可改进路P的定义： 设F是一个可行流，P是从Vs到Vt的一条路，若P满足下列条件： (1)在P的所有前向弧(Vi,Vj)上， 0＜=Fij＜Cij，即P+中的每一条弧是非饱和孤； (2)在P的所有后向弧(Vi,Vj)上， 0＜ Fij＜= Cij ，即P-中的每一条弧是非零流弧。null (1)不属于可改进路P的弧(Vi,Vj)上的流量一概不变，即F1ij＝Fij (2)可改进路P上的所有弧(Vi,Vj)上的流量按下述规则变化； 在前向弧(Vi,Vj)上，F1ij＝Fij+a 在后向弧(Vi,Vj)上， F1ij＝Fij-a a称为可改进量，它应该按照下述原则确定：a既要取得尽量大，又要使变化后的Fij仍满足可行流的两个条件——容量限制条件和平衡条件。不难看出，按照这个原则,a即不能超过每条前向弧的Cij-Fij，也不能超过每条后向弧的Fij。因此a应该等于前向弧上的Cij-Fij与后向弧上的Fij的最小值。nullV1V2V4V6V5V31222220033P: V1 V3  V2 V4 V6P+＝{(Vl,V3)，(V2,V4)，(V4,V6)} P -＝{(V3,V2)}C13-F13＝8-2=6 C24-F24＝4-0=4 C46-F46＝7-2=5 F32＝2nullV1V2V4V6V5V312+2=42-2=0222+2=40+2=2033改进后的Fnull重要结论： 设F是网络D的一个流，如果不存在从Vs到Vt关于F的可改进路P，那么F一定是最大流。 求最大流的基本思路：null 1．标号过程 在这个过程，网络中的顶点或者是标号点(又分为已检查和未检查两种)，或者是未标号点。每个标号点的标号包含两个部分。第一标号指明它的标号从哪一顶点得到，以便找出可改进路；第二个标号是为确定可改进量a用的。 null 标号过程开始，总先给Vs标上(0,+∞)，这时Vs是已标号而未检查的顶点，其余都是未标号点。一般，取一个标号而未检查的顶点Vi，对一切未标号点Vj： (1)若在弧(Vi,Vj)上Fij＜Cij,则给Vj标号(Vi,L(Vj))。这里L(Vj)＝min[L(Vi),Cij-Fij]。这时顶点Vj成为标号而未检查的顶点。 (2)若在弧(Vj ,Vi)上Fij ＞0，则给Vj 标号(- Vi ,L(Vj)),这里L(Vj)＝min[L(Vi), Fij]。这时顶点Vj 成为标号而未检查的顶点。 null在Vi的全部相邻顶点都已标号后，Vi成为标号而已检查过的顶点。重复上述步骤，一旦Vt被标上号，表明得到一条从Vs到Vt的可改进路P，转入调整过程。 若所有标号都已检查过致使标号过程无法继续时算法结束。这时的可行流即最大流。null2．调整过程 采用“倒向追踪”的方法，从Vt开始，利用标号点的第一个标号逐条弧地找出可改进路P，并以Vt 的第二个标号L(Vt)作为改进量a，改进P路上的流量。 重新进入标号过程。nullV1V2V4V6V5V3(0,+∞)(1,4)(1,8)(2,4)(2,1)(4,4)nullV1V2V4V6V5V3(0,+∞)(-4,2)(1,8)(3,2)(4,2)444(3,2)nullV1V2V4V6V5V3(0,+∞)(1,6)(5,2)44622(3,2)(5,2)nullV1V2V4V6V5V3(0,+∞)(1,4)4464222nullconst maxn=100; type nodetype=record{可改进路顶点类型} l,p:integer;{标号、检查标志} end; arctype=record{网顶点类型} c,f:integer;{容量、流量} end; gtype=array[0..maxn,0..maxn] of arctype; ltype=array[0..maxn] of nodetype; var lt:ltype; g:gtype; n,s,t:integer;{顶点数、源点、汇点} f:text;存储结构nullnullnullford(var a:integer):booleannullfulkerson( a:integer)nullV1V2V4V6V5V34478292练习一：用标号法编程计算如图网络的最大流。416nullV1V2V4V6V5V3444+2=62+2=42221—2 4 1—3 4 2—4 4 3—4 2 3—5 2 4—6 6 5—6 2 Max=8练习一：用标号法编程计算如图网络的最大流，输出格式如下所示null练习二：用标号法编程计算如图网络的最大流。null1—2 3 1—3 2 2—4 3 3—5 2 4—6 3 5—6 2 Max=5V1V2V4V6V5V3333222练习二：用标号法编程计算如图网络的最大流。