图论及其应用ppt3

0.810.60.40.20xt00.511.5210.500.51n1Email:[e-mail]图论及其应用任课教师：杨春数学科学学院0.810.60.40.20xt00.511.5210.500.51n2第一章图的基本概念本次课主要内容子图、图运算、路与连通性(一)、子图的相关概念(三)、路与连通性(二)、图运算0.810.60.40.20xt00.511.5210.500.51n31、子图简单地说，图G的任意一部分(包括本身)都称为是图G的的一个子图。定义1如果(一)、子图的相关概念()(),()()VHVGEHEG且H中边的重数不超过G中对应边的条数，则称H为G的子图，记为HG当时，称H是G的真子图，记为,HGHGHG0.810.60.40.20xt00.511.5210.500.51n42、点与边的导出子图(1)图G的顶点导出子图定义2如果，则以为顶点集，以两个端点均在中的边集组成的图，称为图G的点导出子图。记为：()VVG[]GVVV例1如图所示，求。其中[]GV1,3,5V12345图G0.810.60.40.20xt00.511.5210.500.51n5解：由点导出子图的定义得：[]GV135(2)图G的边导出子图定义3如果，则以为边集，以中边的所有端点为顶点集组成的图，称为图G的边导出子图。记为：()EEGEE[]GE例2如图所示，求。其中[]GE13,24,35E0.810.60.40.20xt00.511.5210.500.51n6解：由边导出子图的定义得：12345图G[]GE123450.810.60.40.20xt00.511.5210.500.51n73、图的生成子图定义3如果图G的一个子图包含G的所有顶点，称该子图为G的一个生成子图例2如图所示，求G的所有生成子图123图G解：按边数分别求出0.810.60.40.20xt00.511.5210.500.51n8定理：简单图G=(n,m)的所有生成子图个数为2m(二)、图运算在图论中，将两个或更多的图按照某种方式合并，或者对一个图作某种形式的操作，可以得到很有意义的新图。将图合并或对一个图进行操作，称为图运算。图运算形式很多。1、图的删点、删边运算(1)、图的删点运算设，在G中删去中的顶点和G中与之关联的所有边的操作，称为删点运算。记为()VVGVGV特别地，如果只删去一个点v，则记为G-v.0.810.60.40.20xt00.511.5210.500.51n9(2)、图的删边运算设，在G中删去中的所有边的操作，称为删边运算。记为()EEGEGE特别地，如果只删去一条边e，则记为G-e.注：删点、删边后得到的图是原图的子图。2、图的并运算设G1,G2是G的两个子图，G1与G2并是指由为顶点集，以为边集组成的子图。记为：12()()VGVG12()()EGEG12GG特别是，如果G1,G2不相交(没有公共顶点)，称它们的并为直接并，可以记为：12GG0.810.60.40.20xt00.511.5210.500.51n102、图的交运算设G1,G2是G的两个子图，G1与G2交是指由为顶点集，以为边集组成的子图。记为：12()()VGVG12()()EGEG12GG设G1,G2是两个图，G1与G2的差是指从G1中删去G2中的边得到的新图。记为G1-G2.3、图的差运算4、图的对称差运算(或环和运算)设G1,G2是两个图，G1与G2的对称差定义为：121212()()GGGGGG0.810.60.40.20xt00.511.5210.500.51n11例3已知G1与G2，求12GG12GG12GG21GG12GG1234abcdefG1h2354cdegijG2解：由相应运算定义得下面结果：1234abcdef5hgij12GG234cde12GG0.810.60.40.20xt00.511.5210.500.51n1212GG123abf21GGh2354gij1234abf5hgij12GG0.810.60.40.20xt00.511.5210.500.51n135、图的联运算设G1,G2是两个不相交的图，作G1+G2，并且将G1中每个顶点和G2中的每个顶点连接，这样得到的新图称为G1与G2的联图。记为：12GG例4已知G1与G2，求12GG21G1345G2解：由联图的定义得：2134512GG0.810.60.40.20xt00.511.5210.500.51n146、图的积图设是两个图。对点集111222(,),(,),GVEGVE12VVV的任意两个点u=(u1,u2)与v=(v1,v2),当(u1=v1和u2adjv2)或(u2=v2和u1adjv1)时，把u与v相连。如此得到的新图称为G1与G2的积图。记为12GGG例5已知G1与G2，求12GGGG112G2345(1,4)(1,3)(1,5)(2,3)(2,4)(2,5)12GGG0.810.60.40.20xt00.511.5210.500.51n156、图的合成图设是两个图。对点集111222(,),(,),GVEGVE12VVV的任意两个点u=(u1,u2)与v=(v1,v2),当(u1adjv1)或(u1=v1和u2adjv2)时，把u与v相连。如此得到的新图称为G1与G2的合成图。记为12[]GGG例6已知G1与G2，求G112G234512[]GGG(1,4)(1,3)(1,5)(2,3)(2,4)(2,5)12[]GGG0.810.60.40.20xt00.511.5210.500.51n16图的积运算是网络构造的常用方法。并行计算机中的网络拓扑常采用所谓的“超立方体”结构。采用该结构可使网络具有较好的可靠性、较小的通信延迟和很好的可扩展性以及便于并行编程等优点。“超立方体”可以采用积图来递归构造。定义如下：(1)1方体12QK(2)n方体定义为：21nnQKQQ1Q3Q2“超立方体”常采用下面简单的递归构造方法：0.810.60.40.20xt00.511.5210.500.51n17n方体Qn的顶点可用一个长度为n的二进制码来表示。Qn的顶点数目正好等于2n个。由n-1方体Qn-1构造Qn的方法是：将Qn-1拷贝一个。将原Qn-1每个顶点的码前再添加一个零，将拷贝得来的n-1方体每个顶点的码前面再添加一个1。然后在两个n-1方体之间连线：当且仅当两个顶点码只有一位对应位数字不同时，该两点连线。如此得到的图即为n方体。关于n方体Qn的性质研究，可以查阅到很多文献。经典文章是：SaadY,SchultzMH.Topologicalpropertiesofhypercubes[J].IEEETrans.Comput.1988,37(7):867--8727、图的联合把G1的一个顶点和G2的一个顶点粘合在一起后得到的新图称为G1与G2的联合。记为：12GGG0.810.60.40.20xt00.511.5210.500.51n18(三)、路与连通性对图的路与连通性进行研究，在计算机网络研究中有十分重要的意义。因为网络的抽象就是一个图。研究网络信息传递，信息寻径是主要问题之一，这恰对应于图中路的研究；在网络研究中，可靠性也是主要问题之一，它与图的连通性问题相对应。1、路与连通性的相关概念(1)、图中的途径G的一条途径（或通道或通路）是指一个有限非空序列w=v0e1v1e2v2…ekvk，它的项交替地为顶点和边，使得，ei的端点是vi-1和vi.1ik途径中边数称为途径的长度；v0,vk分别称为途径的起点与终点，其余顶点称为途径的内部点。(2)、图中的迹边不重复的途径称为图的一条迹。0.810.60.40.20xt00.511.5210.500.51n19图中顶点u与v的距离：u与v间最短路的长度称为u与v间距离。记为d(u,v).如果u与v间不存在路，定义d(u,v)=∞.(3)、图中的路(4)、图中两顶点的距离注：起点与终点重合的途径、迹、路分别称为图的闭途径、闭迹与圈。闭迹也称为回路。长度为k的圈称为k圈，k为奇数时称为奇圈，k为偶数时称为偶圈。顶点不重复的途径称为图的一条路。(5)、图中两顶点的连通性图G中点u与v说是连通的，如果u与v间存在通路。否则称u与v不连通。点的连通关系是等价关系。如果图G中任意两点是连通的，称G是连通图，否则，称G是非连通图。非连通图中每一个极大连通部分，称为G的连通分支。G的连通分支的个数，称为G的分支数，记为()G0.810.60.40.20xt00.511.5210.500.51n20(6)、图的直径连通图G的直径定义为：()max(,),()dGduvuvVG如果G不连通，图G的直径定义为()dG例7证明：在n阶连通图中(1)至少有n-1条边；(2)如果边数大于n-1，则至少有一条闭迹；(3)如果恰有n-1条边，则至少有一个奇度点。证明:(1)若G中没有1度顶点，由握手定理：()2()21vVGmdvnmnmn0.810.60.40.20xt00.511.5210.500.51n21若G中有1度顶点u，对G的顶点数作数学归纳。当n=2时，结论显然；设结论对n=k时成立。当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G的边数≥k.另证：由于G连通，所以，存在如下形式的途径：121nnvvvv显然该途径至少含有n-1条边。(v1,v2,…,vn是G的n个不同顶点)(2)考虑G中途径：121:nnWvvvv若W是路，则长为n-1;但由于G的边数大于n-1,因此，存在vi与vj,它们相异，但邻接。于是：1iijivvvv为G中一闭途径，于是也就存在闭迹。0.810.60.40.20xt00.511.5210.500.51n22(3)若不然，G中顶点度数至少为2，于是由握手定理：()2()21vVGmdvnmnmn这与G中恰有n-1条边矛盾！例8证明：若δ≥2，则G中必然含有圈。证明：只就连通图证明即可！设W=v1v2…..vk-1vk是G中的一条最长路。由于δ≥2，所以vk必然有相异于vk-1的邻接顶点。又W是G中最长路,所以，这样的邻接点必然是v1,v2,….,vk-2中之一。设该点为vm，则vmvm+1….vkvm为G中圈。例9设G是具有m条边的n阶单图，证明：若G的直径为2且Δ=n-2,则m≥2n-4.证明：设d(v)=Δ=n-2,且设v的邻接点为v1,v2,…,vn-2.u是剩下的一个顶点。由于d(G)=2且u不能和v邻接，所以u至少和v1,v2…,vn-2中的一个顶点邻接。否则有d(G)2.不妨假设u和v1,v2…vk邻接。0.810.60.40.20xt00.511.5210.500.51n23为了保证u到各点距离不超过2,vk+1,….vn-2这些顶点的每一个必须和前面v1,v2,…,vk中某点邻接，这样，图中至少又有n-2条边。总共至少有2n-4条边。2、连通性性质定理1：若图G不连通，则其补图连通证明：对,如果u,v属于G的同一分支，设w是与u,v处于不同分支中的点，则在G的补图中，u与w,v与w分别邻接，于是，u与v在G的补图中是连通的。,()uvVG0.810.60.40.20xt00.511.5210.500.51n24如果u与v在G的两个不同分支中，则在G的补图中必然邻接，因此，也连通。所以，若G不连通，G的补图是连通的。定理2：设图G为n阶图，若对G中任意两个不相邻顶点u与v，有：()()1dudvn则G是连通的,且d(G)≤2.证明：我们证明，对G中任意两点x与y,一定存在一条长度至多为2的连接x与y的路。若,则上面论断