第4章 网络流与连通度.ppt

实例：现在想将一些物资从起点站S运抵终点站T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。问最多能将多少货物从S运抵T？思考：该实例问题的数学模型如何建立？模型：用顶点表示中转站，每条边代表一条公路，边上的数表示该公路的最大运载量。问题转化为如何在网络中安排最优线路及流量，以求得从发点S到收点T的最大流。,第4章网络流与连通度,网络(network)网络N=(D，w)：其中D=(V,E)是一个有向图，w为边上的权函数。若w表示容量函数c，即每条边a=(u,v)E(D)均有一个容量c(a)0，则称网络N=（D，c）为容量网络。若对任何aE(D)，c(a)都是非负整数，则称N为整容量网络(integercapacitynetwork).网络中有两个特别的顶点：发点s(source,源点)和收点t(sink,汇点)。,第1节网络流,流(flow)网络流是一个对于所有结点u和v都有以下特性的实数函数f:VVR容量约束对所有的u,vV，要求f(u,v)c(u,v)。守恒约束对所有uV/s,t，要求f+(u)=f-(u)。通常把满足上述容量约束和守恒约束的流称为可行流。,第1节网络流,流量(valueofaflow)valf=f+(s)-f-(s)=f-(t)-f+(t)最大流(maximumflow)N中具有最大流量的可行流称为最大流。最大流问题就是求出从源点s到汇点t的最大的流量值。,给定网络N=(D,c)及N上可行流f，设aE(D):若f(a)=c(a)，称a是f饱和的；f(a)0，称a是f正的。边的剩余容量(residualcapacity)是cf(a)=c(a)f(a)。这定义了以RN(D,cf)表示的剩余网络(residualnetwork)，它显示剩余的可用的容量的多少。,第1节网络流,例1网络及网络流。,第1节网络流,思考如何求最大流？（1）零流是一个可行流。（2）先给出一个非零可行流，根据剩余容量判断它的“极大性”，但极大流并不一定是最大流。（3）寻找更一般的方法来增大流。（4）何时达到最大，最大流的上界是什么？,第1节网络流,f-可增路径（f-增广路径）设网络N=(D,c)及N上可行流f，P是网络N中一条路径，对任意aE(P):（1）若P沿a正向前进，令(a)=c(a)-f(a);（2）若P沿a逆向前进，令(a)=f(a);令(P)=min(a):aE(P),称为路径P的公差。显然(P)0。若(P)=0，称P为f-饱和路；若(P)0，称P为f-非饱和路。若P是一条(s,t)路，则为f-非饱和路，则称P为f-可增路。,第1节网络流,第1节网络流,引理1如果P是公差为的一条f-可增路，则将P正向通过的边的流量加上，将P逆向通过的边的流量减去，会产生一个流值增大的可行流f。,由此得到一个一般方法来增大流：,截边集(cutedgeset)（割边集）D中形如(S，S)的有向边集B称为(s,t)截边集，其中sS，tS。有时也将此截边集记为(S，T)。截边集B的容量capB=cap(S,T)=c(B)=c(a)foraB最小截(minimumcutset)（最小割）具有最小容量的(s,t)截边集，称为最小截。,第1节网络流,引理2：如果U是网络中一些顶点构成的一个集合，则从U流出的流量是从U中各个顶点流出的流量的总和。即f+(U)-f-(U)=f+(v)-f-(v)(vU)。特别地，如果f是一个可行流而（S，T）是一个源点/汇点截边集，则从S流出的流量和流入T的流量均为f的流量值valf。,第1节网络流,引理3：如果f是一个可行流而(S，T)是一个源点/汇点截边集，则valf=f+(S)-f-(S)cap(S，T)。由引理3知，具有最小容量的截就产生了流值的最佳上界。从而引出最小截问题。网络中，最大流问题和最小截问题是对偶优化问题。即：如果给定值为n的流和值为n的一个截，则可以证明这个截就是最小截，而这个流就是一个最大流。,第1节网络流,引理4：N中可行流f是一个最大流N不包含f-可增路径。,第1节网络流,定理4.1（最大流最小截定理）在任何容量网络N中，最大流流量等于最小截容量。,推论4.1（整数最大流最小截定理）任何整容量网络N中都存在整数最大流，而且其流量等于最小截容量。,第1节网络流,例1观察下列的一组都是五个顶点的连通图。问：至少要删除多少个点或多少条边后，图不再连通？,第3节连通度,在图（1）中删除一个顶点或删除一条边之后，图不连通。在图（2）中，删除一个顶点之后，或至少需要删除两条边之后，子图才不再连通。在图（3）中，至少需要删除三个顶点；或至少需要删除三条边之后，子图才不连通。在图（4）中，删除顶点集的任何非空真子集之后，子图都连通；但删除四个顶点之后，剩下的只是一个平凡图；又至少需要删除四条边之后子图才不连通。,思考1.如果用(G)和(G)分别表示至少要删除多少个点或多少条边后，图G不再连通，则可能得到哪些性质？2.如何给出(G)和(G)定义？,实例：常用的一些网络，如通讯网、公路网、计算机网络可模型化一个图。图中的点可代表通讯站、城市或处理机，图中的边可代表通讯线、公路或网线。问题：如果上例中的图表示的是四个通讯网络模型，则某些通讯站或通讯线如果出现故障，则通讯将不能正常进行。由此可知图的连通程度与网络的可靠性紧密相关。理论：刻画图的连通程度主要有两个参数点连通度(G)和边连通度(G)。研究图的连通度无论在理论上还是在应用上都有其重要价值。,第3节连通度,定义1设无向图G=(V,E)是连通图，若有顶点集V1V，使图G删除了V1中的所有顶点后,所得到的图G-V1是不连通图，则称V1是G的一个点割集(cut-setofvertices)。G中点数最少的点割集称为最小点割集。最小点割集中的顶点数称为G的点连通度（连通度）。即(G)=min|V1|：V1是G的点割集称为图G的点连通度(vertex-connectivity)。通俗地说，点连通度(G)是使得G不连通所必须删除的点的最小个数。,第3节连通度,定义2设无向图G=(V,E)是连通图，若有边集E1E，使图G中删除了E1的所有边后，所得到的子图是不连通图，则称E1是G的一个边割集(cut-setofedges)。边数最少的边割集称为最小边割集，其所含边数称为图G的边连通度(edge-connectivity)。即边连通度(G)=min|E1|：E1是G的边割集通俗地说，边连通度(G)是使得G不连通所必须删除的边的最小条数。,第3节连通度,注意(1)非平凡连通图G一定具有边割集。(2)非平凡连通图G存在点割集的充要条件是G中至少存在两个不相邻的相异顶点。(3)对不连通的图和平凡图，规定其点连通度和边连通度都是0；对完全图，规定其点连通度为v-1。,第3节连通度,例1对完全图Kn,求(Kn)、(Kn)、(Kn)、(Kn)。,例2对下图G，求(G)、(G)、(G)、(G)。,定义3若一个图的连通度至少为k，则称该图是k连通的。显然，非平凡连通图是1连通的；图G是2连通的当且仅当G连通、无割点且至少含有3个点。定义4若一个图的边连通度至少为k，则称该图是k边连通的。显然，非平凡连通图是1边连通的；图G是2边连通的当且仅当G连通、无割边且至少含有2个点。,第3节连通度,点连通度、边连通度的性质,分析：若G是v阶完全图，则;若G不是完全图,则。考虑顶点u，使得。,返回结束,设G是v阶简单图，则以下几条结论成立：1、,；2、，等号成立当且仅当；3、，等号成立当且仅当；4、对G的任意一个顶点u,；5、对G的任意一条边e,。,定理对任何图G，都有(G)(G)。证法一若G平凡或不连通，则(G)=(G)=0，不等式成立。下设G为非平凡连通图，对(G)用归纳法证明(G)(G)。当(G)=1时,(G)=1。设对(G)k(k2)的图G,均有(G)(G)。对(G)=k的图G，设E是G的一个最小边割集，即|E|=k。取eE，令H=G-e，则(H)=k-1.由归纳假设(H)k-1.（情况1H含完全图作为支撑子图,则G也如此,，此时(G)=(G)k-1.情况2否则，）设S是H的一个最小顶点割，即|S|=(H)k-1。若GS不连通，则(G)|S|(H)k-1.若G-S连通，因H-S不连通，故e是G-S的割边。此时，若G-S中恰含两个顶点，则|V(G)|=|S|+2,于是(G)|V(G)|-1=|S|+1k。若G-S中至少含三个顶点，则G-S有1顶点割v，于是Sv是G的顶点割，从而(G)|Sv|=(H)+1k。所以总有(G)k=(G)。,第3节连通度,定理对任何图G，都有(G)(G)。证法二设G中有个顶点条边。若(G)=0，则(G)=0；若(G)=1，则(G)=1；若(G)-1，因(G)-1,所以(G)(G)；若(G)=且1-1,不防设e1,e2，e是G中最小边割集。这时G-e2，.，e是连通图且e1是它的一条割边。记e1的两个端点为u和v，在e2,e3,e上各取一个不同于u和v的端点（重复不计），这样最多选取-1个顶点，记它们构成的子集为V1。当G-V1不连通时，(G)|V1|-1(G)；当G-V1连通时，e1是G-V1的一条割边且G-V1中至少有2个顶点，因而e1的至少一个端点是G-V1的割点，将这个点增加到V1中得到V2，于是G-V2不连通。所以(G)|V2|=(G)。这个证明表明：当1w(G),则称v为G的一个割点。定义2若V(G)的子集V使得w(GV)w(G),则称V为图G的一个顶点割集。含有k个顶点的顶点割集称为k-顶点割集。注：(1)割点是1顶点割集。(2)完全图没有顶点割集。定义3（点）连通度(G)=min|V|:V是G的顶点割集。对完全图定义(Kv)=v1。若G不连通或是平凡图,则(G)=0。使得|V|=(G)的顶点割集V称为G的最小顶点割集。若(G)k，则称G为k连通的。所有非平凡连通图都是1连通的。无割点的图必是2连通的。,连通性有关内容回顾,定义4设eE(G)，如果w(Ge)w(G)，则称e为G的一条割边。定理1边e是G的割边当且仅当e不在G的任何圈中。定理2一个连通图是树当且仅当它的每条边都是割边。定义5对图G，若E(G)的子集E使得w(GE)w(G)，则称E为图G的一个边割集。含有k条边的边割集称为k-边割集。(1)对非平凡图G，若E是一个边割集，则GE不连通。(2)一条割边构成一个1边割集。(3)设SV(G)，SV(G)，S,S，记号S,S表示一端在S中另一端在S中的所有边的集合。对图G的每个边割集E,必存在非空的SV(G)，使得S,SC=E,其中SC=VS。,连通性有关内容回顾,定义6边连通度(G)=min|S,SC|:SV(G),S。完全图边连通度定义为(K)=1。对平凡图或不连通图G，(G)=0。若图G是含有割边的连通图，则(G)=1。使得|E|=(G)的边割集E称为G的最小边割集。若(G)k，则称G为k边连通的。所有非平凡连通图都是1边连通的。定理3(Whitney不等式)(G)(G)(G)。,连通性有关内容回顾,定理4(Whitney,1932)阶3的图G是2连通图当且仅当G中任二顶点共圈。证明充分性：设G中任二顶点在同一圈上，欲证G是2连通的。对wV(G)，任取u,vV(Gw)。由条件，u,v在G中共处于某个圈C上。若wC，则在Gw中u,v仍在圈C上；若wC，则Gw中u,v在路Cw上。总之u,v在Gw中有路相连。由u,v的任意性，Gw是连通图，故w不是G的割点。再由w的任意性知，G无割点，即G是2连通的。必要性：设G是2连通图，欲证任二顶点u,v都在同一圈上。对距离d(u,v)作归纳法。d(u,v)=1时，因2，故边uv不是割边，Guv仍连通。因此Guv中存在一条(u,v)路P1。这表明在G中u,v都在圈P1+uv上。假定d(u,v)k时，结论成立。下证d(u,v)=k时结论也成立。,连通性有关内容回顾,证明(续)当d(u,v)=k时，设P0=uwv是长为k的一条(u,v)路，则d(u,w)=k1。由归纳法假设，u,w在同一圈上，故在u,w间有两条无公共内部顶点的路P和Q。因G是2连通图，故Gw仍连通。在Gw中存在(u,v)路P。令x是P上最后一个与PUQ的公共顶点（因uPQ，这样的x存在）。不妨设xP，则P上(u,x)段P上(x,v)段与Q+wv是两条内部无公共点的(u,v)路。故u,v在同一圈上。归纳法完成。证毕。,连通性有关内容回顾,推论1图G(3)是2连通图当且仅当G中任二顶点被至少两条内部无公共顶点的路所连。推论2若图G(3)是2连通图，则G的任二边都位于同一圈上。证明：设G是3的2连通图，且e1e2E(G)，在e1和e2上各添加一个新的顶点v1和v2(边的细分)，构成一个新图G。G仍是2连通的。由Whitney定理，v1和v2在G中位于同一个圈上。故e1和e2在G中位于同一个圈上。证毕。注：Whitney定理可推广到k连通图，得到Menger定理：Menger定理1图G(k+1)是k连通图当且仅当G中任二顶点至少被k条内部无公共顶点的路所连。Menger定理2图G是k边连通图当且仅当G中任二顶点至少被k条无公共边的路所连。,连通性有关内容回顾,截边集(cutedgeset)D中形如(S,S)的有向边集B称为(x,y)截边集，其中xS，yS。最小截边集(minimumcut-edgeset)具有最小边数的(x,y)截边集称为最小(x,y)截边集。最小(x,y)截边集的边数称为D的局部边连通度(localedge-connectivity)，用D(x,y)表示。通俗地讲，D的局部边连通度D(x,y)等于删去后就会破坏所有有向(x,y)路的边的最小数目。思考：局部边连通度D(x,y)与最小割B容量capB的关系？,第2节Menger定理,设x和y是图D中不同两顶点，P是D中(x,y)路集。边不交的(x,y)路集(edge-disjoint)若P中任何两条路Pi和Pj均有E(Pi)E(Pj)=，则称P是D中边不交的(x,y)路集。D中边不交的(x,y)路的最大条数用D(x,y)表示。思考：边不交的(x,y)路的最大条数D(x,y)与最大流f的流量valf的关系？,第2节Menger定理,进一步：边不交的(x,y)路的最大条数D(x,y)与D的局部边连通度D(x,y)的关系？,第2节Menger定理,定理4.2.1（Menger定理(边形式)）设x和y是图D中不同两顶点，则D(x,y)=D(x,y)。,推论4.2.1.2（L.Lovsz,1973）D是Euler图D连通，并且对任意两点x,yV(D)，有D(x,y)=D(y,x)。,推论4.2.1.1设x和y是无向图G中任意两顶点，则有G(x,y)=G(x,y)。,设x和y是图D中不同两顶点，P是D中(x,y)路集。内部点不交的(x,y)路集(internallyvertex-disjoint)若P中任何两条路Pi和Pj均有V(Pi)V(Pj)=x,y，则称P是D中内部点不交的(x,y)路集。D中内部点不交的(x,y)路的最大条数用D(x,y)表示。,第2节Menger定理,(x,y)分离集(separatingset)若存在V(D)x,y的子集S使D-S中不存在(x,y)路，则称S为D中(x,y)分离集。最小(x,y)分离集具有最小顶点数目的(x,y)分离集称为最小(x,y)分离集。其顶点数目用D(x,y)表示。,思考：局部点连通度D(x,y)与D(x,y)之间有何关系?显然，D(x,y)D(x,y)。,第2节Menger定理,定理4.2.2（Menger定理(顶点形式)）设x和y是图D中不同两顶点，且ED(x,y)=，则有D(x,y)=D(x,y)。,推论4.2.2.1设x和y是无向图G中任意两顶点，则有D(x,y)=D(x,y)。,第2节Menger定理,定理4.2.1（Menger定理(边形式)）设x和y是图D中不同两顶点，则D(x,y)=D(x,y)。,定理4.2.2（Menger定理(顶点形式)）设x和y是图D中不同两顶点