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

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

2、1,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不相邻。,边边、点点关系为相邻；点边关系才是关联,7/

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

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

5、的顶点集合。由定理1有:,7/25/2020,11,e1 e2 e3 e4 e5,v2 v3,v1,v4,v5,v6,e6,e7,e8,e9,链 由两两相邻的点及其相关联的边构成的点边序列称为链。表达为: v0称为链的起点， vn称为链的终点。 若v0 vn则称该链为开链，反之称为闭链或回路。,7/25/2020,12,e1 e2 e3 e4 e5,v2 v3,v1,v4,v5,v6,e6,e7,e8,e9,简单链 若链中所含的边均不相同，则称为简单链；若边均不相同、点均不相同，则称为初等链或通路。,圈 起点和终点相同的链称为圈。 边不同的圈称为简单圈。,是？ 一条链； 且是开链 也是简单链

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

7、以把不连通图分解成连通的子图来研究。,e1 e2 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的一个部分图/生成

8、子图/支撑子图。(点同边小),导出子图 若V1V2 ，以V1为顶点集，以两端点均在V1中的所有边为边集的子图，称为点导出图，GV1; 若E1E2，以E1为边集，以E1中所有端点为点集的子图，称为边导出图，GE1,7/25/2020,17,无向图 在有些图中，边是没有方向的，即u,v=v,u，这种图称为无向图。,弧 而有些关系具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为弧。,有向图 从顶点u指向v的弧a，记作a=(u,v), (u,v)(v,u)，其中u称为a的起点，v称为a的终点，这样的图称为有向图。 仍以V表示点的集合，以A表示弧的集合，则有向图表示为D=

9、(V, A),7/25/2020,18,Euler回路和中国邮差问题,2,7/25/2020,19,欧拉路：,连通图G中，若存在一条道路，经过每边一次且仅一次，该路称为欧拉道路； 如存在一条回路，则称为欧拉回路。 具有欧拉回路的图，称为欧拉图。,7/25/2020,20,重要定理：,无向连通图是欧拉图，其充分必要条件是：所有的点全是偶点。,证明：,必要性：略。,7/25/2020,21,充分性： 1.设G中每一个节点的度数均为偶数，若能找到一个回路C1使G=C1，则结论成立。 2. 否则，从G中去掉C1后得到子图G,子图中的所有点仍然是偶点。又因为G为连通图，故C1与G至少有一个点重合，设为v

10、i； 3. 在G中从vi出发，重复前面C1的方法，可得到C2； 4. 由于边有限，以此类推，可以将G遍历。,7/25/2020,22,推论： 1. 无向连通图G为欧拉图的充分必要条件：G中的边集可以分为若干个初等回路。 2. 无向连通图G有欧拉道路的充分必要条件：G中有且仅有两个奇点。 3. 有向连通图G为欧拉图的充分必要条件：每个顶点的出次等于入次。,7/25/2020,23,例 一场演出共8个节目，须参加两个以上节目的演员10人。规定节目首尾是AH，或者HA，又每个演员不能连续参加两个节目，求节目安排?,7/25/2020,24,把节目当成对象，研究对象与对象的关系,A,B,C,D,E,F

11、,G,H,经过试探，共发现这样的初等链4条： 1. AFBCGDEH 2. HEDGCBFA 3. AFGCBDEH 4. HEDBCGFA,7/25/2020,25,中国邮差问题：,一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程。 这个问题是由我国数学家管梅谷先生(山东师范大学)在1962年首次提出的，因此在国际上称之为中国邮递员问题。,7/25/2020,26,用图论的述语，在一个连通的赋权图G(V, E)中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回

12、路的权数最小。也就是说要从包含G的每条边的回路中找一条权数最小的回路。 如果G是欧拉图，则以上问题自动解决，但是若G不是欧拉图，则中国由递员问题的解决要困难得多。,7/25/2020,27,设G中有奇点，要求经过每边至少一次，必然有些边要重复，这就相当于在G中增加一些重复边，使所得的新图G没有奇点且满足总路线最短。 由于总路线的长度取决于所增加的重复边的长度，故中国邮差问题可以转化为以下描述： 在G中求一个边集E1E，把G中属于E1的边变成二重边，得到G，G=G+E，使得G中的点全是偶点，且权数最小。,中国邮差问题的实质：,7/25/2020,28,树及最小树问题,3,7/25/2020,29

13、,林 一个没有圈的图称为一个无圈图或称为林。,树 一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。,7/25/2020,30,以下关于树的6种不同描述是等价的：,无圈连通图。 无圈，q=p-1。 连通，q=p-1。 无圈，但若任意增加一条边，则可得到一个且仅一个圈。 连通，但若任意舍弃一条边，图便不连通。 每一对顶点之间有且仅有一条链。,7/25/2020,31,重要定理：,G=(V, E)有生成树的充分必要条件是: G为连通图。,证明：,任取V1V，令V1=v1，由于G是连通图，故V1与V1必有边相连，设相连边为e=(v1,v2),v1V1,v2V1,重复以上步骤，对于ViV，总能

14、找到一个e1，满足一端在Vi中，另一端在Vi中。当i=n时，Vn=v1，v2, ,vn, ET=e1，e2, ,en-1,此时便构成一个生成树。,7/25/2020,32,以上的证明实际给出了寻找支撑树的方法之一：避圈法(加边法), 其中避圈法有可分为深探法和广探法。,深探法：, V中任取一点v，标号为0；, 如某点u已有标号i，检查u的各边，是否其端点已标号；如存在(u,w)边，w未标号，则为w标上i+1，记下(u,w)。令w取代u, 重复；, 如上述这样的边的所有端点均已有标号，则退回标号为i-1的点r, 再重复，直至所有点均已标号为止。,7/25/2020,33,0,1,2,3,4,5,

15、6,7,8,9,10,11,12,13,7/25/2020,34,广探法：, V中任取一点v，标号为0；, 令所有标号为i的点集为Vi，检查Vi的端点是否已标号，对所有为标记的点记下i+1，记下这些边；, 对标记i+1的点再重复，直至所有点均已标号为止。,7/25/2020,35,0,1,3,4,2,1,2,2,3,3,3,3,4,4,7/25/2020,36,最短树问题的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。 在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。 求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，,7/25/2020,37,最小支撑

16、树,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,3,7/25/2020,38,破圈法原理 1.如果网络图中无圈并且q=p-1，则已经是树； 2.如果网络图中有圈，则截去该圈中权数最大的边；这样，并不影响网络图的连通性，且能使边数减少一个； 3.经过一定次数的截边，网络图中将再也没有圈，成为无圈图； 4.如果此时的网络满足q=p-1，则已经是树； 5.由于每次截去的边在圈中具有最大的权数，因此获得的树也是最短的树。,7/25/2020,39,最小支撑树,破圈法,v5,v4,v2,v0,v1,v3,v8,v

17、6,v7,4,1,5,1,1,4,3,5,1,2,5,4,4,2,2,3,7/25/2020,40,避圈法/生长法原理 1.类似于自然界中植物生长的过程，结合就近生长和避免构成圈的要求，逐步生长直到所有的点都已经被包含。 2.如果原网络不连通，则在生长过程中会出现某些点不能被生长，则结束。 3.避圈的原理是已经被包含在生长过的树中的点不再被生长。 4.由于在每次生长时都采用就近生长的方法，生成的树一定是最短树。,7/25/2020,41,避圈法基本思想： 将点集分成两个子集S, S, 在连接两个子集的所有边中选择权数最小的边，则最小边必包含于网络的最小树内。,基本步骤： 从网络中任选一点i作为

18、S； 在连接S与S的所有边中，选择最小边(i, k); 将最小边的另一个端点k从S中移除，纳入S中； 若S为空集，停止运算。否则转,7/25/2020,42,v6,v5,v4,v3,v2,v1,v7,2,4,6,3,1,5,7,1,5,6,4,2,7/25/2020,43,最短路问题,4,7/25/2020,44,最短路问题的一般提法是： 欲寻找网络中从起点v1到终点vn的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。,7/25/2020,45,狄克斯拉(Dijkstra)算法,把V分成两个集合,若vj=vn则已经求得vn到v1的最短路线

19、，否则继续计算,令,计算,求,7/25/2020,46,v9,1,v8,v6,v5,v4,v3,v2,v1,v7,3,4,6,4,10,6,2,2,1,2,(v1,4),3,2,4,6,(,0),(v1,6),(v1,1),7/25/2020,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),7/25/2020,48,逐次逼近算法,用于求指定点v1到网路中任意点的最短路，可适用于有负权的边的网络。,思路： 如果v1到vj的最短路是从v1先到vi，然后再从边(vi,

20、vj)到达vj，那么从v1到vi的这条路必然是v1到vi的最短路。,步骤：,7/25/2020,49,v2,2,v1,-3,-1,v3,4,v4,-2,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,7/25/2020,51,P227例,7/25/2020,52,j,i,v6,v3,v3,7/25/2020,