资源描述
管理运筹学 图 与 网 络 分 析第 7讲 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 3关于图的基本概念 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 4 格尼斯堡7桥难题 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 5 一 、 图 的 概 念所谓图(graph)，就是顶点和边的集合，点的集合记为V (vertex)，边的集合记为E (edge)，则图可以表示为: G=(V, E)，点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 6 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9 ),( 654321 ),e,e,e,e,e,e,e,e(eE 987654321 ,e 211 ,e 212 ,e 413 ,e 314 ,e 315 ,e 426 ,e 437 ,e 448 ,e 549 图的表达： 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 7 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9顶点数(图的阶数) 集合V中元素的个数，记作p(G), 如图中的图G，p(G)=6边数集合E中元素的个数，记作q(G), 如图中的图G，q(G)=9，若e=u,v E，则称u和v为e的端点，而称e为u和v的关联边，也称u，v与边e相关联v1，v2是e1和e2的端点，e1和e2都是v1和v2的关联边。若点u和v与同一条边相关联，则u和v为相邻(邻接)点；若两条边e i和ej有同一个端点，则称ei与ej为相邻边。例如在图中v1和v2为相邻点， v1和v5不相邻；e1与e5为相邻边，e1和e7不相邻。 边边、点点关系为相邻；点边关系才是关联 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 8 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9若一条边的两个端点是同一个顶点，则称该边为环；又若两上端点之间有多于一条边，则称为多重边或平行边。例如图的e8为环; e1, e2为两重边; e4, e5也是两重边。多重图/简单图含有多重边的图称作多重图。无环也无多重边的图称作简单图。无多重边、无环的限制的图称为一般图。完全图任何两个点之间都有且仅有一条边，称作完全图。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 9 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9次(度, degree) 点v作为边的端点的次数，记作d(v)或deg(v)如图中，d(v1)=5, d(v4)=6等端点次为奇数的点称作奇点；次为偶数的点称作偶点。次为1的点称为悬挂点，与悬挂点连接的边称作悬挂边；次为0的点称为孤立点。注意：一个环产生的次为2图中的点v5即为悬挂点，边e9即为悬挂边，而点v6则是弧立点。若图G中所有点都是孤立点，则称图G为空图。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 10 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9重 要 定 理 ：定 理 1 所有顶点的次的和，等于所有边数的2倍。即定 理 2 在任一图中，奇点的个数必为偶数。设V 1和V2分别是图G中次数为奇数和偶数的顶点集合。由定理1有:2qd(v)Vv 2qd(v)d(v) VvVv 1 2 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 11 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9链 由两两相邻的点及其相关联的边构成的点边序列称为链。表达为:v0称为链的起点， vn称为链的终点。若v0 vn则称该链为开链，反之称为闭链或回路。nn1n22110 ,e,e,e 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 12 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9简单链 若链中所含的边均不相同，则称为简单链；若边均不相同、点均不相同，则称为初等链或通路。圈 起点和终点相同的链称为圈。边不同的圈称为简单圈。4312211 ,e,e,e是？一条链；且是开链也是简单链但不是初等链，因为v 1出现2次。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 13 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9是一个圈143746211 ,e,e,e,e是一个简单圈是一个初等圈 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 14 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9连通性 若一个图G的任意两点之间均至少有一条链连接起来，则称这个图G是一个连通图，否则称作不连通图。v1和v6之间没有通路，因此它不是连通图，而如果去掉v6，则构成一个连通图。连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通图分解成连通的子图来研究。 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9子图 G1=(V1,E1), G2=(V2,E2)，如果V1V2 ，又E1E2 ，则称G1是G2的子图。并不是从图G2中任选一些顶点和边在一起就组成G2的子图G1，而只有在G2中的一条边以及连接该边的两个端点均选入G1时，G1才是G2的子图。e1 e2 e3 e4 e5v2 v3v1 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9真子图 当G1中不包含G2中所有的顶点和边，则称G1是G2的真子图。部分图若V1=V2，E1E2 ，则称G1为G2的一个部分图/生成子图/支撑子图。(点同边小) e1 e2 e3 e4 e5v2 v3v1导出子图若V1V2 ，以V1为顶点集，以两端点均在V1中的所有边为边集的子图，称为点导出图，GV1;若E1E2，以E1为边集，以E1中所有端点为点集的子图，称为边导出图，GE1 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 17 e1 e2 e3 e4 e5v2 v3v1v4 v5v6e6 e7e8 e9无向图 在有些图中，边是没有方向的，即u,v=v,u，这种图称为无向图。弧而有些关系具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为弧。有向图从顶点u指向v的弧a，记作a=(u,v), (u,v)(v,u)，其中u称为a的起点，v称为a的终点，这样的图称为有向图。仍以V表示点的集合，以A表示弧的集合，则有向图表示为D=(V, A) 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 18Euler回路和中国邮差问题 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 19 欧拉路：连通图G中，若存在一条道路，经过每边一次且仅一次，该路称为欧拉道路；如存在一条回路，则称为欧拉回路。具有欧拉回路的图，称为欧拉图。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 20 重 要 定 理 ：无向连通图是欧拉图，其充分必要条件是：所有的点全是偶点。证 明 ：必要性：略。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 21 充分性：1.设G中每一个节点的度数均为偶数，若能找到一个回路C1使G=C1，则结论成立。2. 否则，从G中去掉C1后得到子图G,子图中的所有点仍然是偶点。又因为G为连通图，故C1与G至少有一个点重合，设为vi；3. 在G中从vi出发，重复前面C1的方法，可得到C2；4. 由于边有限，以此类推，可以将G遍历。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 22 推论：1. 无向连通图G为欧拉图的充分必要条件：G中的边集可以分为若干个初等回路。2. 无向连通图G有欧拉道路的充分必要条件：G中有且仅有两个奇点。3. 有向连通图G为欧拉图的充分必要条件：每个顶点的出次等于入次。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 23 例 一场演出共8个节目，须参加两个以上节目的演员10人。规定节目首尾是AH，或者HA，又每个演员不能连续参加两个节目，求节目安排?1 2 3 4 5 6 7 8 9 10A B C D E F G H 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 24 把节目当成对象，研究对象与对象的关系1 2 3 4 5 6 7 8 9 10A B C D E F G H A B C D EFGH经过试探，共发现这样的初等链4条：1. AFBCGDEH2. HEDGCBFA3. AFGCBDEH4. HEDBCGFA 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 25 中国邮差问题：一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程。这个问题是由我国数学家管梅谷先生(山东师范大学)在1962年首次提出的，因此在国际上称之为中国邮递员问题。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 26 用图论的述语，在一个连通的赋权图G(V, E)中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的权数最小。也就是说要从包含G的每条边的回路中找一条权数最小的回路。如果G是欧拉图，则以上问题自动解决，但是若G不是欧拉图，则中国由递员问题的解决要困难得多。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 27 设G中有奇点，要求经过每边至少一次，必然有些边要重复，这就相当于在G中增加一些重复边，使所得的新图G没有奇点且满足总路线最短。由于总路线的长度取决于所增加的重复边的长度，故中国邮差问题可以转化为以下描述：在G中求一个边集E1E，把G中属于E1的边变成二重边，得到G，G=G+E，使得G中的点全是偶点，且权数最小。 中国邮差问题的实质： 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 28树及最小树问题 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 29 林 一个没有圈的图称为一个无圈图或称为林。树一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 30 以下关于树的6种不同描述是等价的：无圈连通图。无圈，q=p-1。连通，q=p-1。无圈，但若任意增加一条边，则可得到一个且仅一个圈。连通，但若任意舍弃一条边，图便不连通。 每一对顶点之间有且仅有一条链。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 31 重 要 定 理 ：G=(V, E)有生成树的充分必要条件是: G为连通图。证 明 ：任取V1 V，令V1=v1，由于G是连通图，故V1与V1必有边相连，设相连边为e=(v1,v2),v1 V1,v2 V1重复以上步骤，对于Vi V，总能找到一个e1，满足一端在Vi中，另一端在Vi中。当i=n时，Vn=v1，v2, ,vn, ET=e1，e2, ,en-1,此时便构成一个生成树。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 32 以上的证明实际给出了寻找支撑树的方法之一：避圈法(加边法), 其中避圈法有可分为深探法和广探法。深探法： V中任取一点v，标号为0； 如某点u已有标号i，检查u的各边，是否其端点已标号；如存在(u,w)边，w未标号，则为w标上i+1，记下(u,w)。令w取代u, 重复； 如上述这样的边的所有端点均已有标号，则退回标号为i-1的点r, 再重复，直至所有点均已标号为止。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 330 1 2 345 6789 10 111213 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 34 广探法： V中任取一点v，标号为0； 令所有标号为i的点集为Vi，检查Vi的端点是否已标号，对所有为标记的点记下i+1，记下这些边； 对标记i+1的点再重复，直至所有点均已标号为止。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 350 1 34 21 223 33 344 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 36 最短树问题的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求， 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 37 最 小 支 撑 树K ruskal 算法 v5v4v2v0v1 v3v8 v6v7 41 5114351 25 44 22 3 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 38 破圈法原理1.如果网络图中无圈并且q=p-1，则已经是树；2.如果网络图中有圈，则截去该圈中权数最大的边；这样，并不影响网络图的连通性，且能使边数减少一个；3.经过一定次数的截边，网络图中将再也没有圈，成为无圈图；4.如果此时的网络满足q=p-1，则已经是树；5.由于每次截去的边在圈中具有最大的权数，因此获得的树也是最短的树。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 39 最 小 支 撑 树破圈法 v5v4v2v0v1 v3v8 v6v7 41 5114351 25 44 22 3 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 40 避圈法/生长法原理 1.类似于自然界中植物生长的过程，结合就近生长和避免构成圈的要求，逐步生长直到所有的点都已经被包含。2.如果原网络不连通，则在生长过程中会出现某些点不能被生长，则结束。3.避圈的原理是已经被包含在生长过的树中的点不再被生长。4.由于在每次生长时都采用就近生长的方法，生成的树一定是最短树。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 41 避圈法基本思想：将点集分成两个子集S, S, 在连接两个子集的所有边中选择权数最小的边，则最小边必包含于网络的最小树内。基本步骤： 从网络中任选一点i作为S； 在连接S与S的所有边中，选择最小边(i, k); 将最小边的另一个端点k从S中移除，纳入S中； 若S为空集，停止运算。否则转 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 42v6 v5v4v 3 v2v1 v724 63 157 156 42 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 43最短路问题 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 44 最短路问题的一般提法是：欲寻找网络中从起点v1到终点vn的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 45 狄 克 斯 拉 (Dijkstra)算 法把V分成两个集合,1, 321 nSiS SjTP j)( 0)( 1 )(),(min ijij lPT )( jT)T(min jSj )()( jj TP 若vj=vn则已经求得vn到v1的最短路线，否则继续计算 令计算求 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 46 v91 v8v 6 v5v 4v3 v2v1 v7 346 410622 1 2(v1,4) 3 24 6(,0) (v1,6)(v 1,1) 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 47 v91 v8v 6 v5v 4v3 v2v1 v7 346 410622 1 23 24 6(,0) (,1)(,3)(,5) (,6) (,8) 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 48 逐 次 逼 近 算 法用于求指定点v1到网路中任意点的最短路，可适用于有负权的边的网络。思路：如果v1到vj的最短路是从v1先到vi，然后再从边(vi,vj)到达vj，那么从v1到vi的这条路必然是v1到vi的最短路。步骤：)lmin(PP ij1i1j 1,2,.,n)(jlP 1j(1)1j )lmin(PP ijkjkj )1(1)(1 )1(1)(1 tjtj PP 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 49 v22v1 -3 -1v34v4 -2 v8v7v6 v5 37645 42-3初始条件：P 11(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+,=2 v22v1 -3 -1v34v4 -2 v8v7v6 v5 37645 42-3lij P1j(1) P1j(2) P1j(3) P1j(4) P1j(5) P1j(6) P1j(7) P1j(8)v 1 v2 v3 v4 v5 v6 v7 v8v1 0 2 5 -3 v2 0 -2 4 v3 0 6 v4 4 0 v5 0 v 6 -3 0 4v7 7 2 0 v8 3 -1 0 025-3 020-3611 ji 020-36615 020-3661410 020-336910 020-336910 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 51 P227例 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 52 lij P1j(1) P1j(2) P1j(3) P1j(4) P1j(5) P1j(6) P1j(7) P1j(8)v1 v2 v3 v4 v5 v6 v7 v8v1 0 -1 -2 3v2 6 0 2v3 -3 0 -5 1v4 3 0 2v 5 -1 0v6 1 0 1 7v7 -1 0v8 -3 -5 0 ji 0-5-2-71-150-1-23 0-5-2-7-3-1-56 0-5-2-7-3-1-56 v6 v3 v3 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 53最大流问题 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 54 所谓最大流问题就是在一定的条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题，在最大流问题中一般有如下规定：a. 网络有一个起点vs和一个终点vtb. 网络是有向网络。c. 在网络各条弧上都有一个权，表示允许流过的最大流量。若以bij表示由vi到vj的弧上允许流过的最大流量，以xij表示实际流过该弧的流量，则0 xij bijd. 网络中，除起点v s和终点vt之外的任何顶点，流入量总和应该等于流出量的总和。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 55 设有向联通图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为网络总流量。 廣 東 金 融 學 院 工 商 管 理 系4/22/2021 56 重 要 概 念容量网络G=(V,E,C), vs,vt分别为发、收点，如有边集E为E的子集，将G分为子图G1，G2，其顶点集分别记为 SSVSSSS , vs，vt分别属于 ，且满足：SS,1). G(V, E-E)不连通；2). E为E的真子集，而G(V, E-E)连通则称E为G的割集，记为),( SSE
展开阅读全文