金融学院管理运筹学07图与网络计划技术.ppt

《金融学院管理运筹学07图与网络计划技术.ppt》由会员分享，可在线阅读，更多相关《金融学院管理运筹学07图与网络计划技术.ppt（56页珍藏版）》请在三一办公上搜索。

1、管理运筹学,图与网络分析,第7讲,10/19/2023,3,关于图的基本概念,1,10/19/2023,4,格尼斯堡7桥难题,10/19/2023,5,一、图的概念,所谓图(graph)，就是顶点和边的集合，点的集合记为V(vertex)，边的集合记为E(edge)，则图可以表示为:G=(V,E)，点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。,在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。,10/19/2023,6,图的表达：,10/19/2023,7,e1 e2 e3 e4 e5,v2 v3,

2、v1,v4,v5,v6,e6,e7,e8,e9,顶点数(图的阶数)集合V中元素的个数，记作p(G),如图中的图G，p(G)=6,边数集合E中元素的个数，记作q(G),如图中的图G，q(G)=9，若e=u,vE，则称u和v为e的端点，而称e为u和v的关联边，也称u，v与边e相关联v1，v2是e1和e2的端点，e1和e2都是v1和v2的关联边。,若点u和v与同一条边相关联，则u和v为相邻(邻接)点；若两条边ei和ej有同一个端点，则称ei与ej为相邻边。例如在图中v1和v2为相邻点，v1和v5不相邻；e1与e5为相邻边，e1和e7不相邻。,边边、点点关系为相邻；点边关系才是关联,10/19/202

3、3,8,e1 e2 e3 e4 e5,v2 v3,v1,v4,v5,v6,e6,e7,e8,e9,若一条边的两个端点是同一个顶点，则称该边为环；又若两上端点之间有多于一条边，则称为多重边或平行边。例如图的e8为环;e1,e2为两重边;e4,e5也是两重边。,多重图/简单图含有多重边的图称作多重图。无环也无多重边的图称作简单图。无多重边、无环的限制的图称为一般图。,完全图任何两个点之间都有且仅有一条边，称作完全图。,10/19/2023,9,e1 e2 e3 e4 e5,v2 v3,v1,v4,v5,v6,e6,e7,e8,e9,次(度,degree)点v作为边的端点的次数，记作d(v)或deg

4、(v)如图中，d(v1)=5,d(v4)=6等端点次为奇数的点称作奇点；次为偶数的点称作偶点。次为1的点称为悬挂点，与悬挂点连接的边称作悬挂边；次为0的点称为孤立点。注意：一个环产生的次为2图中的点v5即为悬挂点，边e9即为悬挂边，而点v6则是弧立点。若图G中所有点都是孤立点，则称图G为空图。,10/19/2023,10,e1 e2 e3 e4 e5,v2 v3,v1,v4,v5,v6,e6,e7,e8,e9,重要定理：,定理1 所有顶点的次的和，等于所有边数的2倍。即,定理2 在任一图中，奇点的个数必为偶数。,设V1和V2分别是图G中次数为奇数和偶数的顶点集合。由定理1有:,10/19/20

5、23,11,e1 e2 e3 e4 e5,v2 v3,v1,v4,v5,v6,e6,e7,e8,e9,链 由两两相邻的点及其相关联的边构成的点边序列称为链。表达为:v0称为链的起点，vn称为链的终点。若v0 vn则称该链为开链，反之称为闭链或回路。,10/19/2023,12,e1 e2 e3 e4 e5,v2 v3,v1,v4,v5,v6,e6,e7,e8,e9,简单链 若链中所含的边均不相同，则称为简单链；若边均不相同、点均不相同，则称为初等链或通路。,圈 起点和终点相同的链称为圈。边不同的圈称为简单圈。,是？一条链；且是开链也是简单链但不是初等链，因为v1出现2次。,10/19/2023

6、,13,e1 e2 e3 e4 e5,v2 v3,v1,v4,v5,v6,e6,e7,e8,e9,是一个圈,是一个简单圈,是一个初等圈,10/19/2023,14,e1 e2 e3 e4 e5,v2 v3,v1,v4,v5,v6,e6,e7,e8,e9,连通性 若一个图G的任意两点之间均至少有一条链连接起来，则称这个图G是一个连通图，否则称作不连通图。,v1和v6之间没有通路，因此它不是连通图，而如果去掉v6，则构成一个连通图。,连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通图分解成连通的子图来研究。,e1 e2

7、e3 e4 e5,v2 v3,v1,v4,v5,v6,e6,e7,e8,e9,子图 G1=(V1,E1),G2=(V2,E2)，如果V1V2，又E1E2，则称G1是G2的子图。,并不是从图G2中任选一些顶点和边在一起就组成G2的子图G1，而只有在G2中的一条边以及连接该边的两个端点均选入G1时，G1才是G2的子图。,e1 e2 e3 e4 e5,v2 v3,v1,v4,v5,v6,e6,e7,e8,e9,真子图 当G1中不包含G2中所有的顶点和边，则称G1是G2的真子图。,部分图若V1=V2，E1E2，则称G1为G2的一个部分图/生成子图/支撑子图。(点同边小),导出子图若V1V2，以V1为顶

8、点集，以两端点均在V1中的所有边为边集的子图，称为点导出图，GV1;若E1E2，以E1为边集，以E1中所有端点为点集的子图，称为边导出图，GE1,10/19/2023,17,无向图 在有些图中，边是没有方向的，即u,v=v,u，这种图称为无向图。,弧而有些关系具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为弧。,有向图从顶点u指向v的弧a，记作a=(u,v),(u,v)(v,u)，其中u称为a的起点，v称为a的终点，这样的图称为有向图。仍以V表示点的集合，以A表示弧的集合，则有向图表示为D=(V,A),10/19/2023,18,Euler回路和中国邮差问题,2

9、,10/19/2023,19,欧拉路：,连通图G中，若存在一条道路，经过每边一次且仅一次，该路称为欧拉道路；如存在一条回路，则称为欧拉回路。具有欧拉回路的图，称为欧拉图。,10/19/2023,20,重要定理：,无向连通图是欧拉图，其充分必要条件是：所有的点全是偶点。,证明：,必要性：略。,10/19/2023,21,充分性：1.设G中每一个节点的度数均为偶数，若能找到一个回路C1使G=C1，则结论成立。2.否则，从G中去掉C1后得到子图G,子图中的所有点仍然是偶点。又因为G为连通图，故C1与G至少有一个点重合，设为vi；3.在G中从vi出发，重复前面C1的方法，可得到C2；4.由于边有限，以

10、此类推，可以将G遍历。,10/19/2023,22,推论：1.无向连通图G为欧拉图的充分必要条件：G中的边集可以分为若干个初等回路。2.无向连通图G有欧拉道路的充分必要条件：G中有且仅有两个奇点。3.有向连通图G为欧拉图的充分必要条件：每个顶点的出次等于入次。,10/19/2023,23,例 一场演出共8个节目，须参加两个以上节目的演员10人。规定节目首尾是AH，或者HA，又每个演员不能连续参加两个节目，求节目安排?,10/19/2023,24,把节目当成对象，研究对象与对象的关系,A,B,C,D,E,F,G,H,经过试探，共发现这样的初等链4条：1.AFBCGDEH2.HEDGCBFA3.A

11、FGCBDEH4.HEDBCGFA,10/19/2023,25,中国邮差问题：,一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程。这个问题是由我国数学家管梅谷先生(山东师范大学)在1962年首次提出的，因此在国际上称之为中国邮递员问题。,10/19/2023,26,用图论的述语，在一个连通的赋权图G(V,E)中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的权数最小。也就是说要从包含G的每条边的回路中找一条权数最小的回路。如果G是欧拉图，则以上问题自动解决，

12、但是若G不是欧拉图，则中国由递员问题的解决要困难得多。,10/19/2023,27,设G中有奇点，要求经过每边至少一次，必然有些边要重复，这就相当于在G中增加一些重复边，使所得的新图G没有奇点且满足总路线最短。由于总路线的长度取决于所增加的重复边的长度，故中国邮差问题可以转化为以下描述：在G中求一个边集E1E，把G中属于E1的边变成二重边，得到G，G=G+E，使得G中的点全是偶点，且权数最小。,中国邮差问题的实质：,10/19/2023,28,树及最小树问题,3,10/19/2023,29,林 一个没有圈的图称为一个无圈图或称为林。,树一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。

13、,10/19/2023,30,以下关于树的6种不同描述是等价的：,无圈连通图。无圈，q=p-1。连通，q=p-1。无圈，但若任意增加一条边，则可得到一个且仅一个圈。连通，但若任意舍弃一条边，图便不连通。每一对顶点之间有且仅有一条链。,10/19/2023,31,重要定理：,G=(V,E)有生成树的充分必要条件是:G为连通图。,证明：,任取V1V，令V1=v1，由于G是连通图，故V1与V1必有边相连，设相连边为e=(v1,v2),v1V1,v2V1,重复以上步骤，对于ViV，总能找到一个e1，满足一端在Vi中，另一端在Vi中。当i=n时，Vn=v1，v2,vn,ET=e1，e2,en-1,此时便

14、构成一个生成树。,10/19/2023,32,以上的证明实际给出了寻找支撑树的方法之一：避圈法(加边法),其中避圈法有可分为深探法和广探法。,深探法：,V中任取一点v，标号为0；,如某点u已有标号i，检查u的各边，是否其端点已标号；如存在(u,w)边，w未标号，则为w标上i+1，记下(u,w)。令w取代u,重复；,如上述这样的边的所有端点均已有标号，则退回标号为i-1的点r,再重复，直至所有点均已标号为止。,10/19/2023,33,0,1,2,3,4,5,6,7,8,9,10,11,12,13,10/19/2023,34,广探法：,V中任取一点v，标号为0；,令所有标号为i的点集为Vi，检

15、查Vi的端点是否已标号，对所有为标记的点记下i+1，记下这些边；,对标记i+1的点再重复，直至所有点均已标号为止。,10/19/2023,35,0,1,3,4,2,1,2,2,3,3,3,3,4,4,10/19/2023,36,最短树问题的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，,10/19/2023,37,最小支撑树,Kruskal 算法,v5,v4,v2,v0,v1,v3,v8,v6,v7,4,1,5,1,1,4,3,5,1,2,5,4,4,2,2

16、,3,10/19/2023,38,破圈法原理1.如果网络图中无圈并且q=p-1，则已经是树；2.如果网络图中有圈，则截去该圈中权数最大的边；这样，并不影响网络图的连通性，且能使边数减少一个；3.经过一定次数的截边，网络图中将再也没有圈，成为无圈图；4.如果此时的网络满足q=p-1，则已经是树；5.由于每次截去的边在圈中具有最大的权数，因此获得的树也是最短的树。,10/19/2023,39,最小支撑树,破圈法,v5,v4,v2,v0,v1,v3,v8,v6,v7,4,1,5,1,1,4,3,5,1,2,5,4,4,2,2,3,10/19/2023,40,避圈法/生长法原理 1.类似于自然界中植物

17、生长的过程，结合就近生长和避免构成圈的要求，逐步生长直到所有的点都已经被包含。2.如果原网络不连通，则在生长过程中会出现某些点不能被生长，则结束。3.避圈的原理是已经被包含在生长过的树中的点不再被生长。4.由于在每次生长时都采用就近生长的方法，生成的树一定是最短树。,10/19/2023,41,避圈法基本思想：将点集分成两个子集S,S,在连接两个子集的所有边中选择权数最小的边，则最小边必包含于网络的最小树内。,基本步骤：从网络中任选一点i作为S；在连接S与S的所有边中，选择最小边(i,k);将最小边的另一个端点k从S中移除，纳入S中；若S为空集，停止运算。否则转,10/19/2023,42,v

18、6,v5,v4,v3,v2,v1,v7,2,4,6,3,1,5,7,1,5,6,4,2,10/19/2023,43,最短路问题,4,10/19/2023,44,最短路问题的一般提法是：欲寻找网络中从起点v1到终点vn的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。,10/19/2023,45,狄克斯拉(Dijkstra)算法,把V分成两个集合,若vj=vn则已经求得vn到v1的最短路线，否则继续计算,令,计算,求,10/19/2023,46,v9,1,v8,v6,v5,v4,v3,v2,v1,v7,3,4,6,4,10,6,2,2,1,2

19、,(v1,4),3,2,4,6,(,0),(v1,6),(v1,1),10/19/2023,47,v9,1,v8,v6,v5,v4,v3,v2,v1,v7,3,4,6,4,10,6,2,2,1,2,3,2,4,6,(,0),(,1),(,3),(,5),(,6),(,8),10/19/2023,48,逐次逼近算法,用于求指定点v1到网路中任意点的最短路，可适用于有负权的边的网络。,思路：如果v1到vj的最短路是从v1先到vi，然后再从边(vi,vj)到达vj，那么从v1到vi的这条路必然是v1到vi的最短路。,步骤：,10/19/2023,49,v2,2,v1,-3,-1,v3,4,v4,-2

20、,v8,v7,v6,v5,3,7,6,4,5,4,2,-3,初始条件：,P11(1)=0,P12(1)=2,P13(1)=5,P14(1)=-3,P15(1)=P16(1)=P17(1)=P18(1)=,递推过程：,P11(2)=minP11(1)+l11,P12(1)+l21,P13(1)+l31,P18(1)+l82=min0+0,2+,5+,-3+,=0,P12(2)=minP11(1)+l12,P12(1)+l22,P13(1)+l32,P18(1)+l82=min0+2,2+0,5+,-3+,=2,j,i,10/19/2023,51,P227例,10/19/2023,52,j,i,v

21、6,v3,v3,10/19/2023,53,最大流问题,4,10/19/2023,54,所谓最大流问题就是在一定的条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题，在最大流问题中一般有如下规定：a.网络有一个起点vs和一个终点vtb.网络是有向网络。c.在网络各条弧上都有一个权，表示允许流过的最大流量。若以bij表示由vi到vj的弧上允许流过的最大流量，以xij表示实际流过该弧的流量，则0 xij bijd.网络中，除起点vs和终点vt之外的任何顶点，流入量总和应该等于流出量的总和。,10/19/2023,55,设有向联通图G=(V,E),G中每条边(vi,vj)上有非负数cij，

22、称为边的容量，仅有一个入次为0的点vs称为发点(源)，一个出次为0的点vt称为收点(汇),其余点称为中间点，这样的网络G称为容量网络，记为G=(V,E,C);对任一G中的边(vi,vj)有流量fij,称集合f=fij为网络G上的一个流。满足下列条件的流f为可行流:(1).容量限制:0 fij cij，当fij=cij，称流对边(vi,vj)是饱和的。(2).平衡条件:对于中间点，有fij=fki;对于收、发点，有fsi=fjt=W，称W为网络总流量。,10/19/2023,56,重要概念,容量网络G=(V,E,C),vs,vt分别为发、收点，如有边集E为E的子集，将G分为子图G1，G2，其顶点集分别记为,vs，vt分别属于，且满足：,1).G(V,E-E)不连通；2).E为E的真子集，而G(V,E-E)连通则称E为G的割集，记为,