图与网络分析.ppt

1、第四章 图与网络分析,4.1 基本概念 4.2网络最小费用流问题 4.3网络最大流问题 4.4最短路径问题,4.1 基本概念,图G=(V,E),其中：V= v1,v2,vn E= e1,e2,en,子图 G1=(V1,E1),其中： V1,V ,E1 E,1.图与子图,多重边：两点之间有多于一条边。,环：首尾相接的边,简单图：无环、无多重边的图。,2.有向图与无向图,有向图：有方向的图。 无向图：无方向的图。,e1 V2 V1 e2 V3,v1 e v2,3.关联与相邻,关联（边与点的关系）：若e是v1、v2两点间 的边，记e=v1，v2 ，称v1、v2 与e关联。,相邻（边与边、点与点的关系

2、）： 点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

3、,1,50 70 20 45,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,生成树

4、3,生成树1,/,/,例：用破圈法求右图 的最小支撑树。,4,2,3,1,7 4 5 8 1,总权数=3+4+1=8,4.2.2 求解最小支撑树的避圈法,方法：选边的过程。,步骤：1）从网络中任意选一点vi，找出与vi相关联的权最小的边vi,vj，得第二个顶点vj。,2）把顶点集V分为互补得两部分A,，其中： A：与已选边相关联得点集 ：不与已选边相关联得点集,3) 考虑所有这样的边vi,vj，其中 viA,vj,挑选其中权最小的。,4）重复3），直至全部顶点均属于A即可。,V4,V2,V3,V1,7 4 5 8 1,例：用避圈法求由图的最小 支撑树。,任选点v1，挑与之相关联的权最小的边（

5、v1,v2）.,A= v1,v2,=v3,v4 从边（ v1,v3）,（ v4,v1）, （ v2,v3）, （ v2,v7） 中选权最小的边（ v4,v1）。,V4,V2,V3,V1,7 4 5 8 1,A= v1,v2 ,v4,=v3 从边（ v1,v3）, （ v2,v3）, （ v3,v8） 中选权最小的边（ v2,v3）。, A= v1,v2 , v3， v4,网络的生成树和线性规划的关系,网络的一个生成树对应于线性规划的一个基 生成树上的边对应于线性规划的基变量 生成树的弦对应于线性规划的非基变量 生成树的变换对应于线性规划单纯形法的进基和离基变换,4.3 最短路问题,问题：求网络

6、中一定点到其它点的最短路。,4.3.1 最短路问题的Dijstra解法,方法：给vi点标号wi,vk 其中：wi：vi点到起点vs的最短距离 vk: vi的前接点,方法：(1) 给起点vs标号0，vs。,（2）把顶点集v分为互补的两部分A和 其中：A：已标号点集 ：未标号点集,（3）考虑所有这样的边vi, vj, 其中vi A,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

7、,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,计算min 0+2, 0+1, 0+3= min 2,1,3=1 v4: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=min 2,3,11,3=2 v2:2,v1,0,v1,1,v1,2

8、,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,计算min 0+3, 2+6, 2+5, 1+2=min 3,8,7,3=3 v6: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,计算 min 2+6, 2+5, 1

9、+2, 3+4=min 8,7,3,7=3 v7: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,计算min 2+6, 2+5, 3+3, 3+8=min 8,7,6,11=6 v5: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,v

10、6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(7)A=V1,V2,V4,V6,V7,计算min 2+6, 6+9, 6+4, 3+8=min 8,15,10,11=8 v3: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,计算 min 8+6, 6+4, 3+7=min 14,10,11=10 v8:10,v5,2,v

11、1,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,

12、vj)上的容量。现D上要安排通过一个流f=fij，其中fij为弧(vi,vj)上的流量。,问题：如何安排流量fij，可使D上通过 的总流量V(f)最大？,边的容量和流量 容量cij，流量fij 可行流 满足以下条件的流称为可行流： 1、每一个节点流量平衡 2、0fij cij,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到

13、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和，使s E,t ,称弧集（ E，)= (i,j) | i E,j 为D的截集。,截量：截集上的

14、容量之和。记为C(E, ).,6.流量与截量的关系,任何一个可行流的流量V(f)都不会超过任一截量。即V(f) C(E, ),最大流-最小截定理：max V(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)+

15、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

16、,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;可调整流量为：=1； 调整链的流量为： xij=xij+1; f=f+1=2,v1,7,v1,2,-v3,2,v2,2,v5,(3)调整流量f=2,继续求出网络的一条不饱和链.,v2,v3,v5,v4,v6,v7,v1,f=2,f=2,(6,1),(3,0),(7,1),(9,1),(2,0),(4,0),(4,0),(3,0),(7,0),(8,1),(1,1),(8

17、,1),v1,7,v1,5,v2,5,v5,可增广链为：v7-v5-v2-v1;可调整流量为：=5； 调整链的流量为： xij=xij+5, f=f+5=2+5=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,6),v1,3,v5,6,v1,4,v3,4,v4,可增广链为：v7-v5-v4-v3-v1;可调整流量为：=3, 调整链上的流量为： xij=xij+3, f=f+3=7+3=10,(

18、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,6),v1,3,v6,1,v3,3,v1,3,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

19、),(4,3),(3,1),(7,0),(8,2),(8,6),v1,3,v1,(6,6),f=11,(1,1),2,v1,网络已不存在可增广链，因此，当前流达到最大流。,(7)已求得最大流 f=11,v2,v3,v5,v4,v6,v7,v1,f=11,(6,6),(2,0),(4,3),(3,0),(7,5),(4,4),(3,1),(1,1),(7,0),(9,9),(8,2),(8,6),f=11,最小割集为(v,v)=(v2,v5),(v3,v4),(v3,v5) 最小割集容量为C(v,v)=f25+f34+f35=6+4+1=11,网络最小费用流问题,b2=-2,b4=3,b3=5,

20、b5=-6,b6=-5,b1=5,c24=5,c46=1,c13=3,c35=2,c56=4,c34=4,c12=6,cij 单位流量的费用,初始基础可行解生成树,b6=-5,b2=-2,b4=3,b3=5,b5=-6,b1=5,x13=3,x46=3,x35=8,x56=2,x12=2,2,3,4,5,6,1,确定非基变量x24和x34,b2=-2,b6=-5,b3=5,b5=-6,b1=5,c24=5,c46=1,c13=3,c35=2,c56=4,c34=4,c12=6,2,3,4,5,6,1,b4=3,求x24的检验数z24-c24 闭回路法,z24 -c24 =(-c46+c56+c35+c13-c12)-c24=(-1+4+2+3-6)-5=-3,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,c24=5,c46=1,c13=3,c35=2,c56=4,c12=6,2,3,4,5,6,1,求x34的检验数z34 -c34