管理运筹学-07-图与网络计划技术

管理运筹学图与网络分析第7讲廣東金融學院工商管理系2/17/20203关于图的基本概念廣東金融學院工商管理系2/17/20204格尼斯堡7桥难题廣東金融學院工商管理系2/17/20205一、图的概念所谓图(graph)，就是顶点和边的集合，点的集合记为V(vertex)，边的集合记为E(edge)，则图可以表示为:G=(V,E)，点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。廣東金融學院工商管理系2/17/20206e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9),υ,υ,υ,υ,υ(υυ654321),e,e,e,e,e,e,e,e(eE987654321],υ[υe211],υ[υe212],υ[υe413],υ[υe314],υ[υe315],υ[υe426],υ[υe437],υ[υe448],υ[υe549图的表达：廣東金融學院工商管理系2/17/20207e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9顶点数(图的阶数)集合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为相邻(邻接)点；若两条边ei和ej有同一个端点，则称ei与ej为相邻边。例如在图中v1和v2为相邻点，v1和v5不相邻；e1与e5为相邻边，e1和e7不相邻。边边、点点关系为相邻；点边关系才是关联廣東金融學院工商管理系2/17/20208e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9若一条边的两个端点是同一个顶点，则称该边为环；又若两上端点之间有多于一条边，则称为多重边或平行边。例如图的e8为环;e1,e2为两重边;e4,e5也是两重边。多重图/简单图含有多重边的图称作多重图。无环也无多重边的图称作简单图。无多重边、无环的限制的图称为一般图。完全图任何两个点之间都有且仅有一条边，称作完全图。廣東金融學院工商管理系2/17/20209e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9次(度,degree)点v作为边的端点的次数，记作d(v)或deg(v)如图中，d(v1)=5,d(v4)=6等端点次为奇数的点称作奇点；次为偶数的点称作偶点。次为1的点称为悬挂点，与悬挂点连接的边称作悬挂边；次为0的点称为孤立点。注意：一个环产生的次为2图中的点v5即为悬挂点，边e9即为悬挂边，而点v6则是弧立点。若图G中所有点都是孤立点，则称图G为空图。廣東金融學院工商管理系2/17/202010e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9重要定理：定理1所有顶点的次的和，等于所有边数的2倍。即定理2在任一图中，奇点的个数必为偶数。设V1和V2分别是图G中次数为奇数和偶数的顶点集合。由定理1有:2qd(v)Vv2qd(v)d(v)VvVv12廣東金融學院工商管理系2/17/202011e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9链由两两相邻的点及其相关联的边构成的点边序列称为链。表达为:v0称为链的起点，vn称为链的终点。若v0≠vn则称该链为开链，反之称为闭链或回路。nn1n22110,υ,e,υ,υ,e,υ,eυ廣東金融學院工商管理系2/17/202012e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9简单链若链中所含的边均不相同，则称为简单链；若边均不相同、点均不相同，则称为初等链或通路。圈起点和终点相同的链称为圈。边不同的圈称为简单圈。4312211,υ,e,υ,e,υ,eυ是……？一条链；且是开链也是简单链但不是初等链，因为v1出现2次。廣東金融學院工商管理系2/17/202013e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9是一个圈143746211,υ,e,υ,e,υ,e,υ,eυ是一个简单圈是一个初等圈廣東金融學院工商管理系2/17/202014e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9连通性若一个图G的任意两点之间均至少有一条链连接起来，则称这个图G是一个连通图，否则称作不连通图。v1和v6之间没有通路，因此它不是连通图，而如果去掉v6，则构成一个连通图。连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通图分解成连通的子图来研究。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9子图G1=(V1,E1),G2=(V2,E2)，如果V1V2，又E1E2，则称G1是G2的子图。并不是从图G2中任选一些顶点和边在一起就组成G2的子图G1，而只有在G2中的一条边以及连接该边的两个端点均选入G1时，G1才是G2的子图。e1e2e3e4e5v2v3v1e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9真子图当G1中不包含G2中所有的顶点和边，则称G1是G2的真子图。部分图若V1=V2，E1E2，则称G1为G2的一个部分图/生成子图/支撑子图。(点同边小)e1e2e3e4e5v2v3v1导出子图若V1V2，以V1为顶点集，以两端点均在V1中的所有边为边集的子图，称为点导出图，G[V1];若E1E2，以E1为边集，以E1中所有端点为点集的子图，称为边导出图，G[E1]廣東金融學院工商管理系2/17/202017e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9无向图在有些图中，边是没有方向的，即[u,v]=[v,u]，这种图称为无向图。弧而有些关系具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为弧。有向图从顶点u指向v的弧a，记作a=(u,v),(u,v)≠(v,u)，其中u称为a的起点，v称为a的终点，这样的图称为有向图。仍以V表示点的集合，以A表示弧的集合，则有向图表示为D=(V,A)廣東金融學院工商管理系2/17/202018Euler回路和中国邮差问题廣東金融學院工商管理系2/17/202019欧拉路：连通图G中，若存在一条道路，经过每边一次且仅一次，该路称为欧拉道路；如存在一条回路，则称为欧拉回路。具有欧拉回路的图，称为欧拉图。廣東金融學院工商管理系2/17/202020重要定理：无向连通图是欧拉图，其充分必要条件是：所有的点全是偶点。证明：必要性：略。廣東金融學院工商管理系2/17/202021充分性：1.设G中每一个节点的度数均为偶数，若能找到一个回路C1使G=C1，则结论成立。2.否则，从G中去掉C1后得到子图G’,子图中的所有点仍然是偶点。又因为G为连通图，故C1与G’至少有一个点重合，设为vi；3.在G’中从vi出发，重复前面C1的方法，可得到C2；4.由于边有限，以此类推，可以将G遍历。廣東金融學院工商管理系2/17/202022推论：1.无向连通图G为欧拉图的充分必要条件：G中的边集可以分为若干个初等回路。2.无向连通图G有欧拉道路的充分必要条件：G中有且仅有两个奇点。3.有向连通图G为欧拉图的充分必要条件：每个顶点的出次等于入次。廣東金融學院工商管理系2/17/202023[例]一场演出共8个节目，须参加两个以上节目的演员10人。规定节目首尾是AH，或者HA，又每个演员不能连续参加两个节目，求节目安排?12345678910ABCDEFGH廣東金融學院工商管理系2/17/202024把节目当成对象，研究对象与对象的关系12345678910ABCDEFGHABCDEFGH经过试探，共发现这样的初等链4条：1.AFBCGDEH2.HEDGCBFA3.AFGCBDEH4.HEDBCGFA廣東金融學院工商管理系2/17/202025中国邮差问题：一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程。这个问题是由我国数学家管梅谷先生(山东师范大学)在1962年首次提出的，因此在国际上称之为中国邮递员问题。廣東金融學院工商管理系2/17/202026用图论的述语，在一个连通的赋权图G(V,E)中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的权数最小。也就是说要从包含G的每条边的回路中找一条权数最小的回路。如果G是欧拉图，则以上问题自动解决，但是若G不是欧拉图，则中国由递员问题的解决要困难得多。廣東金融學院工商管理系2/17/202027设G中有奇点，要求经过每边至少一次，必然有些边要重复，这就相当于在G中增加一些重复边，使所得的新图G’没有奇点且满足总路线最短。由于总路线的长度取决于所增加的重复边的长度，故中国邮差问题可以转化为以下描述：在G中求一个边集E1E，把G中属于E1的边变成二重边，得到G’，G’=G+E，使得G’中的点全是偶点，且权数最小。中国邮差问题的实质：廣東金融學院工商管理系2/17/202028树及最小树问题廣東金融學院工商管理系2/17/202029林一个没有圈的图称为一个无圈图或称为林。树一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。廣東金融學院工商管理系2/17/202030以下关于树的6种不同描述是等价的：无圈连通图。无圈，q=p-1。连通，q=p-1。无圈，但若任意增加一条边，则可得到一个且仅一个圈。连通，但若任意舍弃一条边，图便不连通。每一对顶点之间有且仅有一条链。廣東金融學院工商管理系2/17/202031重要定理：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},此时便构成一个生成树。廣東金融學院工商管理系2/17/202032以上的证明实际给出了寻找支撑树的方法之一：避圈法(加边法),其中避圈法有可分为深探法和广探法。深探法：V中任取一点v，标号为0；如某点u已有标号i，检查u的各边，是否其端点已标号；如存在(u,w)边，w未标号，则为w标上i+1，记下(u,w)。令w取代u,重复；如上述这样的边的所有端点均已有标号，则退回标号为i-1的点r,再重复，直至所有点均已标号为止。廣東金融學院工商管理系2/17/202033012345678910111213廣東金融學院工商管理系2/17/202034广探法：V中任取一点v，标号为0；令所有标号为i的点集为Vi，检查Vi的端点是否已标号，对所有为标记的点记下i+1，记下这些边；对标记i+1的点再重复，直至所有点均已标号为止。廣東金融學院工商管理系2/17/20203501342122333344廣東金融學院工商管理系2/17/202036最短树问题的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，廣東金融學院工商管理系2/17/202037最小支撑树Kruskal算法v5v4v2v0v1v3v8v6v74151143512544223廣東金融學院工商管理系2/17/202038破圈法原理1.如果网络图中无圈并且q=p-1，则已经是树；2.如