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

管理运筹学图与网络分析图与网络分析第7讲廣東金融學院工商管理系关于图的基本概念5/26/20243廣東金融學院工商管理系格尼斯堡格尼斯堡7桥难题桥难题5/26/20244廣東金融學院工商管理系一、图的概念一、图的概念所谓图(graph)，就是顶点和边的集合，点的集合记为V(vertex)，边的集合记为E(edge)，则图可以表示为:G=(V,E)，点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。5/26/20245廣東金融學院工商管理系e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9图的表达：图的表达：5/26/20246廣東金融學院工商管理系e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9顶点数顶点数(图的阶数图的阶数)集合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不相邻。边边、点点关系为相邻；点边关系才是关联5/26/20247廣東金融學院工商管理系e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9若一条边的两个端点是同一个顶点，则称该边为环环；又若两上端点之间有多于一条边，则称为多重边多重边或平行边平行边。例如图的e8为环;e1,e2为两重边;e4,e5也是两重边。多重图多重图/简单图简单图含有多重边的图称作多重图多重图。无环也无多重边的图称作简单图简单图。无多重边、无环的限制的图称为一般图一般图。完全图完全图任何两个点之间都有且仅有一条边，称作完全完全图图。5/26/20248廣東金融學院工商管理系e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9次次(度度,degree)点v作为边的端点的次数，记作d(v)或deg(v)如图中，d(v1)=5,d(v4)=6等端点次为奇数的点称作奇点奇点；次为偶数的点称作偶点偶点。次为1的点称为悬挂点悬挂点，与悬挂点连接的边称作悬挂边悬挂边；次为0的点称为孤立点孤立点。注意：一个环环产生的次为2图中的点v5即为悬挂点，边e9即为悬挂边，而点v6则是弧立点。若图G中所有点都是孤立点，则称图G为空图空图。5/26/20249廣東金融學院工商管理系e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9重要定理：重要定理：定理定理1 所有顶点的次的和，等于所有边数的2倍。即定理定理2 在任一图中，奇点的个数必为偶数。设V1和V2分别是图G中次数为奇数和偶数的顶点集合。由定理1有:5/26/202410廣東金融學院工商管理系e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9链链 由两两相邻的点及其相关联的边构成的点边序列称为链链。表达为:v0称为链的起点起点，vn称为链的终点终点。若v0 vn则称该链为开链开链，反之称为闭链闭链或回路回路。5/26/202411廣東金融學院工商管理系e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9简单链简单链 若链中所含的边均不相同，则称为简单链简单链；若边均不相同、点均不相同，则称为初等链初等链或通通路路。圈圈 起点和终点相同的链称为圈圈。边不同的圈称为简单圈简单圈。是？一条链链；且是开链开链也是简单链简单链但不是不是初等链初等链，因为v1出现2次。5/26/202412廣東金融學院工商管理系e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9是是一个圈圈是是一个简单圈简单圈是是一个初等圈初等圈5/26/202413廣東金融學院工商管理系e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9连通性连通性 若一个图G的任意两点之间均至少有一条链连接起来，则称这个图G是一个连通图连通图，否则称作不连通图不连通图。v1和v6之间没有通路，因此它不是不是连通图，而如果去掉v6，则构成一个连通图。连通连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通图分解成连通的子图来研究。5/26/202414e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9子图子图 G1=(V1,E1),G2=(V2,E2)，如果V1V2，又E1E2，则称G1是G2的子图子图。并不是从图G2中任选一些顶点和边在一起就组成G2的子图G1，而只有在G2中的一条边以及连接该边的两个端点均选入G1时，G1才是G2的子子图图。e1 e2 e3 e4 e5v2 v3v15/26/202415e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9真子图真子图 当G1中不包含G2中所有的顶点和边，则称G1是G2的真子图真子图。部分图部分图若V1=V2，E1E2，则称G1为G2的一个部分图部分图/生成子图生成子图/支撑子图支撑子图。(点同边小)e1 e2 e3 e4 e5v2 v3v1导出子图导出子图若V1V2，以V1为顶点集，以两端点均在V1中的所有边为边集的子图，称为点导出图，GV1;若E1E2，以E1为边集，以E1中所有端点为点集的子图，称为边导出图，GE15/26/202416廣東金融學院工商管理系e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9无向图无向图 在有些图中，边是没有方向的，即u,v=v,u，这种图称为无向图无向图。弧弧而有些关系具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为弧弧。有向图有向图从顶点u指向v的弧a，记作a=(u,v),(u,v)(v,u)，其中u称为a的起点，v称为a的终点，这样的图称为有向图有向图。仍以V表示点的集合，以A表示弧的集合，则有向图表示为D=(V,A)5/26/202417廣東金融學院工商管理系Euler回路和中国邮差问题5/26/202418廣東金融學院工商管理系欧拉路：欧拉路：连通图G中，若存在一条道路，经过每边一次且仅一次，该路称为欧拉道路；如存在一条回路，则称为欧拉回路。具有欧拉回路的图，称为欧拉图。5/26/202419廣東金融學院工商管理系重要定理：重要定理：无向连通图是欧拉图，其充分必要条件是：所有的点全是偶点。证明：证明：必要性必要性：略。5/26/202420廣東金融學院工商管理系充分性充分性：1.设G中每一个节点的度数均为偶数，若能找到一个回路C1使G=C1，则结论成立。2.否则，从G中去掉C1后得到子图G,子图中的所有点仍然是偶点。又因为G为连通图，故C1与G至少有一个点重合，设为vi；3.在G中从vi出发，重复前面C1的方法，可得到C2；4.由于边有限，以此类推，可以将G遍历。5/26/202421廣東金融學院工商管理系推论：推论：1.无向连通图G为欧拉图的充分必要条件：G中的边集可以分为若干个初等回路。2.无向连通图G有欧拉道路的充分必要条件：G中有且仅有两个奇点。3.有向连通图G为欧拉图的充分必要条件：每个顶点的出次等于入次。5/26/202422廣東金融學院工商管理系例例 一场演出共8个节目，须参加两个以上节目的演员10人。规定节目首尾是AH，或者HA，又每个演员不能连续参加两个节目，求节目安排?12345678910ABCDEFGH5/26/202423廣東金融學院工商管理系把节目当成对象，研究对象与对象的关系12345678910A BCDEFGHABCDEFGH经过试探，共发现这样的初等链4条：1.AFBCGDEH2.HEDGCBFA3.AFGCBDEH4.HEDBCGFA5/26/202424廣東金融學院工商管理系中国邮差问题：中国邮差问题：一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程。这个问题是由我国数学家管梅谷先生(山东师范大学)在1962年首次提出的，因此在国际上称之为中国邮递员问题。5/26/202425廣東金融學院工商管理系用图论的述语，在一个连通的赋权图G(V,E)中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的权数最小。也就是说要从包含G的每条边的回路中找一条权数最小的回路。如果G是欧拉图，则以上问题自动解决，但是若G不是欧拉图，则中国由递员问题的解决要困难得多。5/26/202426廣東金融學院工商管理系设G中有奇点，要求经过每边至少一次，必然有些边要重复，这就相当于在G中增加一些重复边，使所得的新图G没有奇点且满足总路线最短。由于总路线的长度取决于所增加的重复边的长度，故中国邮差问题可以转化为以下描述：在G中求一个边集E1E，把G中属于E1的边变成二重边，得到G，G=G+E，使得G中的点全是偶点，且权数最小。中国邮差问题的实质：中国邮差问题的实质：5/26/202427廣東金融學院工商管理系树及最小树问题5/26/202428廣東金融學院工商管理系林林 一个没有圈的图称为一个无圈图无圈图或称为林林。树树一个连通的无圈图则称为树树，一个林的每个连通子图都是一个树。5/26/202429廣東金融學院工商管理系以下关于树的6种不同描述是等价的：无圈连通图。无圈，q=p-1。连通，q=p-1。无圈，但若任意增加一条边，则可得到一个且仅一个圈。连通，但若任意舍弃一条边，图便不连通。每一对顶点之间有且仅有一条链。5/26/202430廣東金融學院工商管理系重要定理：重要定理：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,此时便构成一个生成树。5/26/202431廣東金融學院工商管理系以上的证明实际给出了寻找支撑树的方法之一：避圈法避圈法(加边法),其中避圈法有可分为深探法和广探法。深探法：深探法：V中任取一点v，标号为0；如某点u已有标号i，检查u的各边，是否其端点已标号；如存在(u,w)边，w未标号，则为w标上i+1，记下(u,w)。令w取代u,重复；如上述这样的边的所有端点均已有标号，则退回标号为i-1的点r,再重复，直至所有点均已标号为止。5/26/202432廣東金融學院工商管理系0123456789101112135/26/202433廣東金融學院工商管理系广探法：广探法：V中任取一点v，标号为0；令所有标号为i的点集为Vi，检查Vi的端点是否已标号，对所有为标记的点记下i+1，记下这些边；对标记i+1的点再重复，直至所有点均已标号为止。5/26/202434廣東金融學院工商管理系013421223333445/26/202435廣東金融學院工商管理系最短树问题最短树问题的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，5/26/202436廣東金融學院工商管理系最小支撑树Kruskal 算法算法v5v4v2v0v1v3v8v6v741511435125442235/26/202437廣東金融學院工商管理系破圈法原理破圈法原理1.如果网络图中无圈并且q=p-1，则已经是树；2.如果网络图中有圈，则截去该圈中权数最大的边；这样，并不影响网络图的连通性，且能使边数减少一个；3.经过一定次数的截边，网络图中将再也没有圈，成为无圈图；4.如果此时的网络满足q=p-1，则已经是树；5.由于每次截去的边在圈中具有最大的权数，因此获得的树也是最短的树。5/26/202438廣東金融學院工商管理系最小支撑树破圈法破圈法v5v4v2v0v1v3v8v6v741511435125442235/26/202439廣東金融學院工商管理系避圈法避圈法/生长法原理生长法原理 1.类似于自然界中植物生长的过程，结合就近生长和避免构成圈的要求，逐步生长直到所有的点都已经被包含。2.如果原网络不连通，则在生长过程中会出现某些点不能被生长，则结束。3.避圈的原理是已经被包含在生长过的树中的点不再被生长。4.由于在每次生长时都采用就近生长的方法，生成的树一定是最短树。5/26/202440廣東金融學院工商管理系避圈法基本思想：将点集分成两个子集S,S,在连接两个子集的所有边中选择权数最小的边，则最小边必包含于网络的最小树内。基本步骤：从网络中任选一点i作为S；在连接S与S的所有边中，选择最小边(i,k);将最小边的另一个端点k从S中移除，纳入S中；若S为空集，停止运算。否则转5/26/202441廣東金融學院工商管理系v6v5v4v3v2v1v72463157156425/26/202442廣東金融學院工商管理系最短路问题5/26/202443廣東金融學院工商管理系最短路问题的一般提法是：欲寻找网络中从起点v1到终点vn的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。5/26/202444廣東金融學院工商管理系狄克斯拉(Dijkstra)算法把V分成两个集合若vj=vn则已经求得vn到v1的最短路线，否则继续计算 令计算求5/26/202445廣東金融學院工商管理系v91v8v6v5v4v3v2v1v734641062212(v1,4)3246(,0)(v1,6)(v1,1)5/26/202446廣東金融學院工商管理系v91v8v6v5v4v3v2v1v7346410622123246(,0)(,1)(,3)(,5)(,6)(,8)5/26/202447廣東金融學院工商管理系逐次逼近算法用于求指定点v1到网路中任意点的最短路，可适用于有负权的边的网络。思路：思路：如果v1到vj的最短路是从v1先到vi，然后再从边(vi,vj)到达vj，那么从v1到vi的这条路必然是v1到vi的最短路。步骤：步骤：5/26/202448廣東金融學院工商管理系v22v1-3-1v34v4-2v8v7v6v53764542-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+,=0P12(2)=minP11(1)+l12,P12(1)+l22,P13(1)+l32,P18(1)+l82 =min0+2,2+0,5+,-3+,=25/26/202449v22v1-3-1v34v4-2v8v7v6v53764542-3lijP1j(1)P1j(2)P1j(3)P1j(4)P1j(5)P1j(6)P1j(7)P1j(8)v1v2v3v4v5v6v7v8v1025-3v20-24v306v440v50v6-304v7720v83-10025-3020-3611ji020-36615020-3661410020-336910020-3369105/26/202450廣東金融學院工商管理系P227例例 5/26/202451廣東金融學院工商管理系lijP1j(1)P1j(2)P1j(3)P1j(4)P1j(5)P1j(6)P1j(7)P1j(8)v1v2v3v4v5v6v7v8v10-1-23v2602v3-30-51v4302v5-10v61017v7-10v8-3-50ji0-5-2-71-150-1-230-5-2-7-3-1-560-5-2-7-3-1-56v6v3v35/26/202452廣東金融學院工商管理系最大流问题5/26/202453廣東金融學院工商管理系所谓最大流问题就是在一定的条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题，在最大流问题中一般有如下规定：a.网络有一个起点vs和一个终点vtb.网络是有向网络。c.在网络各条弧上都有一个权，表示允许流过的最大流量。若以bij表示由vi到vj的弧上允许流过的最大流量，以xij表示实际流过该弧的流量，则0 xij bijd.网络中，除起点vs和终点vt之外的任何顶点，流入量总和应该等于流出量的总和。5/26/202454廣東金融學院工商管理系设有向联通图G=(V,E),G中每条边(vi,vj)上有非负数cij，称为边的容量，仅有一个入次为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为网络总流量。5/26/202455廣東金融學院工商管理系重要概念容量网络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的割集，记为5/26/202456