图与网络分析.ppt

第四章图与网络分析,4.1基本概念4.2网络最小费用流问题4.3网络最大流问题4.4最短路径问题,4.1基本概念,图G=(V,E),其中：V=v1,v2,vnE=e1,e2,en,子图G1=(V1,E1),其中：V1,V,E1E,1.图与子图,多重边：两点之间有多于一条边。,环：首尾相接的边,简单图：无环、无多重边的图。,2.有向图与无向图,有向图：有方向的图。无向图：无方向的图。,e1V2V1e2V3,v1ev2,3.关联与相邻,关联（边与点的关系）：若e是v1、v2两点间的边，记e=v1，v2，称v1、v2与e关联。,相邻（边与边、点与点的关系）：点v1与v2有公共边，称点v1与v2相邻；边e1与e2有公共点，称边e1与e2相邻。,圈（Circuit）封闭的链称为圈如：=(1,2),(2,4),(3,4),(1,3,链:由图G中的某些点与边相间构成的序列V1,e1,V2,e2,Vk,ek,若满足ei=Vi,Vi,则称此点边序列为G中的一条链。如：=(1,2),(3,2),(3,4),4.链、圈与连通图,4,2,3,1,4,2,3,1,连通图任意两个节点之间至少有一条链的图称为连通图,4,2,3,1,5.网络,给图中的点和边赋以具体的含义和权数（如距离、费用、容量等），则称这样的图为网络图。,4,2,3,1,50702045,4.2最小支撑树问题,树：无圈的连通图，记为T。,树的性质,2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,如果树T有m个结点，则边的个数为m-1。,树中任意两个节点间有且只有一条链。,在树中任意去掉一条边，则不连通。,图的支撑树,若图G=(V,E)的子图T=(V,E)是树，则称T为G的支撑树。,4.2.1求解最小支撑树问题的破圈法,方法：去边破圈的过程。,步骤：1）在给定的赋权的连通图上任找一个圈。2）在所找的圈中去掉一条权数最大的边。3）若所余下的图已不含圈，则计算结束，余下的图即为最小支撑树，否则返回1）。,生成树2,生成树3,生成树1,/,/,例：用破圈法求右图的最小支撑树。,4,2,3,1,74581,总权数=3+4+1=8,网络的生成树和线性规划的关系,网络的一个生成树对应于线性规划的一个基生成树上的边对应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树的变换对应于线性规划单纯形法的进基和离基变换,4.3最短路问题,问题：求网络中一定点到其它点的最短路。,4.3.1最短路问题的Dijstra解法,方法：给vi点标号wi,vk其中：wi：vi点到起点vs的最短距离vk:vi的前接点,方法：(1)给起点vs标号0，vs。,（2）把顶点集v分为互补的两部分A和其中：A：已标号点集：未标号点集,（3）考虑所有这样的边vi,vj,其中viA,vj挑选其中与vs距离最短的点vj标号minwi+cij,vi,(4)重复（3），直至终点vt标上号wt,vk，则wt即为vs至vt的最短距。反向追踪可求得最短路。,例：求v1至v8的最短路。,v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(1)v1:0,v1,计算min0+2,0+1,0+3=min2,1,3=1v4:1.v1,1,v1,0,v1,(2)A=v1,检查边（v1,v2),(v1,v4),(v1,v3),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(3)A=v1,v4,计算min0+2,0+3,1+10,1+2=min2,3,11,3=2v2:2,v1,0,v1,1,v1,2,v1,考虑边（v1,v2),(v1,v6),(v4,v2),(v4,v7),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,（4）A=v1,v2,v4,计算min0+3,2+6,2+5,1+2=min3,8,7,3=3v6:3,v1,2,v1,1,v1,0,v1,3,v1,考虑边（v1,v6),(v2,v3),(v2,v5),(v4,v7),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(5)A=V1,V2,V4,V6,计算min2+6,2+5,1+2,3+4=min8,7,3,7=3v7:3,v4,2，V1,1，V1,0，V1,3，V1,3,v4,考虑边(v2,v3),(v2,v5),(v4,v7),(v6,v7),V2,V3,V7,V1,V8,V4,V5,V6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(6)A=V1,V2,V4,V6,V7,计算min2+6,2+5,3+3,3+8=min8,7,6,11=6v5:6,v7,2,v1,1,v1,0,v1,3,v1,3,v4,6,v7,考虑边(v2,v3),(v2,v5),(v7,v5),(v7,v8),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(7)A=V1,V2,V4,V6,V7,计算min2+6,6+9,6+4,3+8=min8,15,10,11=8v3:8,v2,2,V1,1,V1,0,V1,3,V1,3,V4,6,V7,8,v2,考虑边(v2,v3),(v5,v3),(v5,v8),(v7,v8),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(8)A=v1,v2,v3,v4,v6,v7,计算min8+6,6+4,3+8=min14,10,11=10v8:10,v5,2,v1,1,v1,0,v1,3,v1,3,v4,6,v7,8,v2,10,v5,考虑边（v3,v8),(v5,v8),(v7,v8),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(9)A=v1,v2,v3,v4,v6,v7,v8,v1到v10的最短路径为v1v4v7v5v8，最短路长度为10。,2,v1,1,v1,0,v1,3,v1,3,v4,6,v7,8,v2,10,v5,反向追踪：v8-v5-v7-v4-v1,4.4最大流问题,问题的一般提法：,有一网络D=(V,A,C),其中V：点集；A：弧集；C=cij,cij为弧（vi,vj)上的容量。现D上要安排通过一个流f=fij，其中fij为弧(vi,vj)上的流量。,问题：如何安排流量fij，可使D上通过的总流量V(f)最大？,边的容量和流量容量cij，流量fij可行流满足以下条件的流称为可行流：1、每一个节点流量平衡2、0fijcij,1.边的容量和流量、可行流,4.4.1网络流的基本概念与基本定理,2.饱和边、不饱和边、流量的间隙,（1，2）是饱和的,2、如果fijcuij，边从i到j的方向是不饱和的；,（1，2）是不饱和的间隙为12=c12-f12=5-3=2,1、如果fij=cij，边从i到j的方向是饱和的；,3、如果xij=0，边从j到i的方向是饱和的；,（2，1）是饱和的,如果fij0，边从j到i的方向是不饱和的；,（2，1）是不饱和的间隙为12=f12=5,4.可增广链（或可扩充链）,网络D中st的链，记为+：前向弧（与方向一致）-：后向弧（与方向相反）,若链上的流量满足：所有的前向弧皆未饱和，后向弧皆非零，则称为D中关于可行流fij的可增广链。,(4,2)(3,1)(5,3)(4,1)(3,2),5.截集与截量,截集：将容量网络中的起点与终点分开并使流中断的一组正向弧的集合。,即将顶点V分为二个非空互补集E和，使sE,t,称弧集（E，)=(i,j)|iE,j为D的截集。,截量：截集上的容量之和。记为C(E,).,6.流量与截量的关系,任何一个可行流的流量V(f)都不会超过任一截量。即V(f)C(E,),最大流-最小截定理：maxV(f)minC(E,),判别最大流的条件：可行流f是最大流D中不存在关于f的可增广链,4.4.2最大流问题的标号解法,步骤：先找一个可行流检验调整,过程：标号找一条可增广链。给vi标号i,vk，其中i为可增值上限，vk为vi的前接点。对于下一个标号点vj,标号如下：,j,vi:其中j=minj,cij-fij(vi,vj)+j,-vi:其中j=minj,fij(vi,vj)-,调整流量：fij+t(vi,vj)+fij=fij-t(vi,vj)-fij其它,例：求结点至结点的最大流，同时写出其最小截集及截量。,解：（1）给出一个可行流f=0，找到一条从v1到v7的不饱和链,可增广链为：v7-v6-v3-v1；可调整流量为：=1调整链的流量：xij=xij+；f=f+1=1,v2,v3,v5,v4,v6,v7,v1,f=0,f=0,(6,0),(2,0),(4,0),(7,0),(4,0),(3,0),(7,0),(9,0),(3,0),(1,0),(8,0),(8,0),，v1,8,v1,3,v2,1,v3,1,v6,（2）调整流量f=1,继续求出网络的一条不饱和链。,v2,v3,v5,v4,v6,v7,v1,f=1,f=1,(6,0),(3,1),(7,0),(9,0),(2,0),(4,0),(4,0),(3,0),(7,0),(8,1),(1,1),(8,1),可增广链为：v7-v5-v2-v3-v1;可调整流量为：=2；调整链的流量为：xij=xij+2;f=f+2=3,v1,7,v1,2,-v3,2,v2,2,v5,(3)调整流量f=2,继续求出网络的一条不饱和链.,v2,v3,v5,v4,v6,v7,v1,f=3,f=3,(6,2),(3,3),(7,2),(9,2),(2,0),(4,0),(4,0),(3,0),(7,0),(8,1),(1,1),(8,1),v1,7,v1,4,v2,4,v5,可增广链为：v7-v5-v2-v1;可调整流量为：=4；调整链的流量为：xij=xij+4,f=f+4=3+4=7,(4)调整流量f=7,继续求出网络的一条不饱和链.,v2,v3,v5,v4,v6,v7,v1,f=7,f=7,(6,6),(3,0),(7,1),(9,6),(2,0),(4,0),(4,0),(3,0),(7,0),(8,1),(1,1),(8,5),v1,3,v5,6,v1,4,v3,4,v4,可增广链为：v7-v5-v4-v3-v1;可调整流量为：=3,调整链上的流量为：xij=xij+3,f=f+3=7+3=10,(5)调整流量f=10,继续求出网络的一条不饱和链.,v2,v3,v5,v4,v6,v7,v1,f=10,f=10,(3,0),(7,4),(9,9),(2,0),(4,3),(4,3),(3,0),(7,0),(8,1),(8,5),v1,1,v6,1,v3,3,v1,1,v4,(6,6),可增广链为：v7-v6-v4-v3-v1;可调整流量为：=1；调整链上的流量为：xij=xij+1,f=f+1=10+1=11,(1,1),(6)调整流量f=11,继续求出网络的一条不饱和链.,v2,v3,v5,v4,v6,v7,v1,f=11,(3,0),(7,5),(9,9),(2,0),(4,4),(4,3),(3,1),(7,0),