网络最大流问题

1.应用背景在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题,控制系统中的信息流问题，常见的人流，物流，水流，气流，电流，现金流等。在一定条件下,求解给定系统的最大流量,就是网络最大流问题.网络系统最大流问题是图与网络理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。一引言2.问题描述连通网络G(V,A)中有m个节点,n条弧,弧eij上的流量上界为cij,求从起始节点vs到终点vt的最大流量的问题就是最大流问题。3.引例连接某产品产地v1和销地v6的交通网如下：v2v5348v3v1v4v65106111735（a）弧（vi，vj）：从vi到vj的运输线，弧旁数字：这条运输线的最大通过能力—容量。v2v5313v3v1v4v61563222（b）制定一个运输方案，使从v1运到v6的产品数量最多。弧旁数字：运输数量—流量。问题：这个运输网络中，从v1到v6的最大输送量是多少？1、网络与流设一个赋权有向图D=（V,A）,在V中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于D中的每一个弧（vi,vj）∈A,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，A，C）。弧的容量：是对网络上的每条弧(vi,vj)都给出一个最大的通过能力，记为c(vi,vj)或简写为cij。二、基本概念sts’t’对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收点,并将其分别与各发点、收点连起来（见图），就可以转换为只含一个发点和一个收点的网络。所以一般只研究具有一个发点和一个收点的网络•流：加在网络各条弧上的一组负载量•f(vi,vj)：加在弧(vi,vj)上的负载量简记为fij，为非负数网络上的流：是指定义在弧集合上的一个函数f={f(vi,vj)},其中f(vi,vj)称为弧（vi,vj)上的流量，流也可看作一个双下标变量弧的流量f(vi,vj)：表示弧(vi,vj)上每单位时间内的实际通过能力弧的容量c(vi,vj)：表示弧（vi,vj)上每单位时间内的最大通过能力零流：网络上所有的fij=0图10-24表示的就是这个网络上的一个流（运输方案），每一个弧上的流量fij就是运输量。例如：f12=1,f13=2,f24=3等等。v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt图10-24v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt对于实际的网络系统上的流，有几个显著的特点：(1)发点的净流出量和收点的净流入量必相等。(2)每一个中间点的流入量与流出量的代数和等于零。(3)每一个弧上的流量不能超过它的最大通过能力（即容量）称满足下列条件的流为可行流：（1）容量限制条件：对于每一个弧（vi,vj）∈A有0f(vi,vj)c(vi,vj)（简记为0fijcij）A)v,v(A)v,v(sjjsjssj)f(vffA)v,v(A)v,v(tjjtjttj)f(vff2、可行流与最大流（2）平衡条件：①对于发点vs，有②对于收点vt，有式子中V(f)称为可行流f的流量,即发点的净输出量（或收点的净输入量）。③对于中间点:流入量=流出量。即对每个i(i≠s,t)有f(vi,vj)-f(vj,vi)=0(is，t)(简记为fij-fji=0(is，t))即总流量=发点的净输出量=收点的净输入量容量网络的可行流总是存在的，如当所有弧的流均取零，即对所有的i,j,有f(vi,vj)=0就是一个可行流可行流中fij＝cij的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧。fij＞0的弧为非零流弧，fij＝0的弧叫做零流弧。2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)图中为零流弧，都是非饱和弧。),(63vv就是要求一个流{fij},使其流量v(f)达到最大,并且满足0fijcijti)f(vt,si0si)f(vffjiij网络的最大流:•求网络的最大流，即是指满足容量限制条件和平衡条件的条件下，使v(f)值达到最大.容量网络D，若μ为网络中从vs到vt的一条链，给μ定向为从vs到vt，μ上的弧分为两类：凡与μ方向相同的称为前向弧，凡与μ方向相反的称为后向弧，其集合分别用μ+和μ-表示。链的方向：若µ是联结vs和vt的一条链，定义链的方向是从vs到vt。3、增广链stf1c1f4c4f5c5f20f30增广链：f是一个可行流，如果满足：)v,v(cf0)v,v(cf0jijijijijiji即中的每一条弧都是非饱和弧即中的每一条弧都是非零流弧则称μ为从vs到vt的关于f的一条增广链。stf1c1f4c4f5c5f20f30v2v53-34-18-3v3v1v4v65-110-511-66-317-23-25-2µ=(v1,v2,v3,v4,v5,v6)µ+={(v1,v2),(v2,v3),(v3,v4),(v5,v6)}µ-={(v5,v4)}后向弧2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)7766633232211),,(,),,(,),,(,),,(,vvvvvvvvvvvvv),(),,(),,(766321vvvvvv),(23vv是一个增广链显然图中增广链不止一条4、截集与截量容量网络D=（V，A，C），vs为始点，vt为终点。如果把V分成两个非空集合使，则所有始点属于V1，而终点属于的弧的集合称为是分离vs和vt的截集（或割）11V,V1t1sVv,Vv)V,V(111Vv2v53(3)4（1）8(3）v3v1v4v65（1）10（5)11(66（3017(2)3（2）5（2）=(v1,v2,v3)V1V1=(v4,v5,v6)=(v1,v2,v3)V1V1=(v4,v5,v6)截集为黄色弧集：)v,v(,)v,v(,)v,v(,)v,v()V,V(5343425211v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2)V,V(11vsv1v2v4v3vt374556378V1)v,v(V2s1)v,v,v,v(Vt4311)v,v(,)v,v(,)v,v()V,V(32421s1118567)V,V(C23241s11)V,V(C11截集中所有弧的容量之和，称为这个截集的容量，记为)V,V()j,i(ji1111)v,v(c)V,V(c，也称截量，则有：2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1))v,v(),v,v(),v,v()V,V(75423121设5211,,vvvV则截集为：76432,,,vvvvV不是该集中的弧和而)v,v()v,v(5423截量为242v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)设，211,vvV则截集为765432,,,,vvvvvV),(),,(),(),(52423121vvvvvvVV截量为20VV截集截集的容量sv1,v2,v3,v4,t(s,1)(s,2)15s,v1v2,v3,v4,t(s,2)(1,2)(1,3)21s,v2v1,v3,v4,t(s,1)(2,4)17s,v1,v2v3,v4,t(1,3)(2,4)18s,v1,v3v2,v4,t(s,2)(1,2)(3,2)(3,t)19s,v2,v4v1,v3,t(s,1)(4,3)(4,t)24s,v1,v2,v3v4,t(2,4)(3,t)14s,v1,v2,v4v3,t(1,3)(4,3)(4,t)25s,v1,v2,v3,v4t(3,t)(4,t)15sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)截集与可行流无关，而只与网络本身有关最小截量是个定值对应的截量也不相同，其中截量最小的截集称为最小截集。设f为网络D=（V，A，C）的任一可行流，流量为v(f)，)V,V(C)f(v11)V,V(11为任一截集，则有结论1：由于V与V的分解方法不同，所以截集就不相同即任何一个可行流的流量都不会超过任一截集的容量f(VV)，ij(i,j)(V,V)ji(j,i)(V,V)f(V,V)f(v,v)f(V,V)f(v,v)stVVVVv(f)f(V,V)f(V,V)的流量等于割到的流量去割的流量，即　　　　若对割和割用表示割中所有方向的弧的流量的总和，表示割中所有方向的弧的流量的总和，则，割的流量有f(VV)，)V,V(VVVV)V,V(v(f)≤f(V,V)≤c(V,V)所以有：2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)stVVVVv(f)f(V,V)f(V,V)的流量等于割到的流量去割的流量，即　　　　v(f)≤f(V,V)≤c(V,V)所以有：****v(f)stv(f)=f(V,V)-f(V,V)若代表网络中从的最大流　　　　　*****v(f)f(V,V)f(V,V)f(V,V)c(V,V)任一可行流的流量≤任一截集的容量v(f)≤v＊(f)≤c＊(v,v)≤c(v,v)由此式可知，当某一流量等于某一截量，即：即所有的v(f)≤v＊(f)，v＊(f)=c＊(v,v)，有如下结论：且所有的c(v,v)≥c＊(v,v)v＊(f)一定是D上的最大流，而一定是D的最小截集的截量。)V,V(C*)V,V(C)f(v*1*1*满足条件那么f*一定是D上的最大流，而如果网络上的一个可行流f*,和网络中的一个截集)V,V(*1*1一定是D的最小截集。)V,V(*1*1结论2：0iii(cf)minfiiif,ff,f,所有再令　所有当f有增广链存在时，找出stf1c1f4c4f5c5f20f30证明：定理8：可行流f是D的最大流的充分必要条件是不存在从vs到vt的关于f的一条增广链。先证f是D的最大流时，则D中一定没有增广链，用反证法非增广链上的弧显然f′仍是一个可行流，(因满足容量限制条件和平衡条件）但和原来的可行流f比较，这时网络中从s→t的流量增大了一个θ值（θ0）.因此：当f有增广链时，f不是最大流，即f是最大流时，f就一定没有增广链下面证明当f没有增广链时，f一定是最大流证明：若网络中没有增广链，则对它构造一个点的集合V*，定义(1)sV*(2)若iV*和f(i,j)c(i,j),则jV*;若iV*和f(j,i)0,则jV*(3)若iV*和f(i,j)=c(i,j),则jV*若iV*和f(j,i)=0,则jV*显然*Vt,否则将存在st的增广链，与假设矛盾.由此为该网络的一个割，该割的容量为*)V*,V(*)V*,V(c则V*=V-V*,满足：由上面定义，通过这个割的流有：0(i,j)(V,V)(i,j)(V,V)(j,i)(V,V)f(V*,V*)f(i,j)c(i,j)c(V*,V*)f(V*,V*)f(j,i)　　　　　　2v(f)f(V*,V*)f(V*,V*)c(V*,V*)c(V*,V*)(1)v(f)c(V*,V*)()　　又12,式与式同成立