《图论课件、子图的相关概念.ppt》由会员分享，可在线阅读，更多相关《图论课件、子图的相关概念.ppt（29页珍藏版）》请在三一办公上搜索。
1、1,图论及其应用,应用数学学院,2,第一章 图的基本概念,本次课主要内容,子图、图运算、路与连通性,(一)、子图的相关概念,(三)、路与连通性,(二)、图运算,3,1、子图,简单地说，图G的任意一部分(包括本身)都称为是图G的的一个子图。,定义1 如果,(一)、子图的相关概念,且H中边的重数不超过G中对应边的条数，则称H为G的子图，记为,当 时，称H是G的真子图，记为,4,2、点与边的导出子图,(1)图G的顶点导出子图,定义2 如果，则以 为顶点集，以两个端点均在 中的边集组成的图，称为图G的点导出子图。记为：,例1 如图所示，求。其中,5,解：由点导出子图的定义得：,(2)图G的边导出子图,
2、定义3 如果，则以 为边集，以 中边的所有端点为顶点集组成的图，称为图G的边导出子图。记为：,例2 如图所示，求。其中,6,解：由边导出子图的定义得：,7,3、图的生成子图,定义3 如果图G的一个子图包含G的所有顶点，称该子图为G的一个生成子图,例2 如图所示，求G的所有生成子图,解：按边数分别求出,8,定理：简单图G=(n,m)的所有生成子图个数为2m,(二)、图运算,在图论中，将两个或更多的图按照某种方式合并，或者对一个图作某种形式的操作，可以得到很有意义的新图。将图合并或对一个图进行操作，称为图运算。图运算形式很多。,1、图的删点、删边运算,(1)、图的删点运算,设，在G中删去 中的顶点
3、和G中与之关联的所有边的操作，称为删点运算。记为,特别地，如果只删去一个点v，则记为G-v.,9,(2)、图的删边运算,设，在G中删去 中的所有边的操作，称为删边运算。记为,特别地，如果只删去一条边e，则记为G-e.,注：删点、删边后得到的图是原图的子图。,2、图的并运算,设G1,G2是G的两个子图，G1与G2并是指由 为顶点集，以 为边集组成的子图。记为：,特别是，如果G1,G2不相交(没有公共顶点)，称它们的并为直接并，可以记为：,10,2、图的交运算,设G1,G2是G的两个子图，G1与G2交是指由 为顶点集，以 为边集组成的子图。记为：,设G1,G2是两个图，G1与G2的差是指从G1中删
4、去G2中的边得到的新图。记为G1-G2.,3、图的差运算,4、图的对称差运算(或环和运算),设G1,G2是两个图，G1与G2的对称差定义为：,11,例3 已知G1与G2，求,解：由相应运算定义得下面结果：,12,13,5、图的联运算,设G1,G2是两个不相交的图，作G1+G2，并且将G1中每个顶点和G2中的每个顶点连接，这样得到的新图称为G1与G2的联图。记为：,例4 已知G1与G2，求,解：由联图的定义得：,14,6、图的积图,设 是两个图。对点集,的任意两个点u=(u1,u2)与v=(v1,v2),当(u1=v1和u2adjv2)或(u2=v2和u1adjv1)时，把u与v相连。如此得到的
5、新图称为G1与G2的积图。记为,例5 已知G1与G2，求,15,6、图的合成图,设 是两个图。对点集,的任意两个点u=(u1,u2)与v=(v1,v2),当(u1adjv1)或(u1=v1和u2adjv2)时，把u与v相连。如此得到的新图称为G1与G2的合成图。记为,例6 已知G1与G2，求,16,图的积运算是网络构造的常用方法。并行计算机中的网络拓扑常采用所谓的“超立方体”结构。采用该结构可使网络具有较好的可靠性、较小的通信延迟和很好的可扩展性以及便于并行编程等优点。,“超立方体”可以采用积图来递归构造。定义如下：,(1)1方体,(2)n方体定义为：,“超立方体”常采用下面简单的递归构造方法
6、：,17,n方体Q n的顶点可用一个长度为n的二进制码来表示。Q n的顶点数目正好等于2n个。,由n-1方体Q n-1构造Q n的方法是：将Q n-1拷贝一个。将原Q n-1每个顶点的码后再添加一个零，将拷贝得来的n-1方体每个顶点的码前面再添加一个1。然后在两个n-1方体之间连线：当且仅当两个顶点码只有一位对应位数字不同时，该两点连线。如此得到的图即为n方体。,关于n方体Q n的性质研究，可以查阅到很多文献。经典文章是：Saad Y,Schultz M H.Topological properties of hypercubes J.IEEETrans.Comput.1988,37(7):8
7、67-872,7、图的联合,把G1的一个顶点和G2的一个顶点粘合在一起后得到的新图称为G1与G2的联合。记为：,18,(三)、路与连通性,对图的路与连通性进行研究，在计算机网络研究中有十分重要的意义。因为网络的抽象就是一个图。研究网络信息传递，信息寻径是主要问题之一，这恰对应于图中路的研究；在网络研究中，可靠性也是主要问题之一，它与图的连通性问题相对应。,1、路与连通性的相关概念,(1)、图中的途径,G的一条途径（或通道或通路）是指一个有限非空序列w=v0 e1 v1 e2 v2ek vk，它的项交替地为顶点和边，使得，ei的端点是vi-1和vi.,途径中边数称为途径的长度；v0,vk分别称为
8、途径的起点与终点，其余顶点称为途径的内部点。,(2)、图中的迹,边不重复的途径称为图的一条迹。,19,图中顶点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中任意两点是连通的，称
9、G是连通图，否则，称G是非连通图。非连通图中每一个极大连通部分，称为G的连通分支。G的连通分支的个数，称为G的分支数，记为,20,(6)、图的直径,连通图G的直径定义为：,如果G不连通，图G的直径定义为,例6 证明：在n阶连通图中,(1)至少有n-1条边；,(2)如果边数大于n-1，则至少有一条闭迹；,(3)如果恰有n-1条边，则至少有一个奇度点。,证明:(1)若G中没有1度顶点，由握手定理：,21,若G中有1度顶点u，对G的顶点数作数学归纳。,当n=2时，结论显然；设结论对n=k时成立。,当n=k+1时，考虑G-u,它仍然为连通图，所以，边数k-1.于是G的边数k.,另证：由于G连通，所以，
10、存在如下形式的途径：,显然该途径至少含有n-1条边。(v1,v2,v n是G的n个不同顶点),(2)考虑G中途径：,若W是路，则长为n-1;但由于G的边数大于n-1,因此，存在vi与vj,它们相异，但邻接。于是：,为G中一闭途径，于是也就存在闭迹。,22,(3)若不然，G中顶点度数至少为2，于是由握手定理：,这与G中恰有n-1条边矛盾！,例7 证明：若2，则G中必然含有圈。,证明：只就连通图证明即可！,设W=v1v2.vk-1vk是G中的一条最长路。由于2，所以vk必然有相异于vk-1的邻接顶点。又W是G中最长路所以，这样的邻接点必然是v1,v2,.,vk-2中之一。设该点为vm，则vmvm+
11、1.v kvm为G中圈。,例8 设G是具有m条边的n阶单图，证明：若G的直径为2且=n-2,则m2n-4.,证明：设d(v)=n-2,且设v的邻接点为v1,v2,vn-2.u是剩下的一个顶点。由于d(G)=2且u不能和v邻接，所以u必须和v1,v2,vn-2中每个顶点邻接。否则有d(G)2.于是得：m2n-4.,23,例8的说明图为：,2、连通性性质,定理1：若图G不连通，则其补图连通,证明：对,如果u,v属于G的同一分支，设w是与u,v处于不同分支中的点，则在G的补图中，u与w,v与w分别邻接，于是，u与v在G的补图中是连通的。,24,如果u与v在G的两个不同分支中，则在G的补图中必然邻接，
12、因此，也连通。,所以，若G不连通，G的补图是连通的。,定理2：设图G为n阶图，若对G中任意两个不相邻顶点u与v，有：,则G是连通的,且d(G)2.,证明：我们证明，对G中任意两点x与y,一定存在一条长度至多为2的连接x与y的路。,若,则上面论断成立！若,可以证明，存在点w，它与x,y同时邻接。,若不然，在G的剩下的n-2个顶点中，假设有k个与x邻接，但与y不邻接，有l个顶点和y邻接，但不和x邻接，同时假定有m个顶点,25,和x,y 均不邻接。则：d(x)=k-1,d(y)=l-1。由于k+l+m=n-2,所以，d(x)+d(y)=k+l-2n-4,矛盾！,推论：设图G为n阶图，若(n-1)/2
13、,则 G 连通。,证明：对G中任意两个不相邻顶点u与v，有：,所以，G是连通的。,注意：定理2的界是紧的(Sharpness)。即不能再修改！,例如：设G由两个分支作成的图，两个分支均为Km,则G中不相邻顶点度数之和恰为n-2.(n=2m),3、偶图的判定定理,26,定理3 一个图是偶图当且当它不包含奇圈。,证明：必要性：设G是具有二分类（X,Y）的偶图，并且C=v0 v1 vk v0是G的一个圈,不失一般性，可假定。一般说来，,。又因为，所以,由此即得C是偶圈。,充分性：在G中任意选取点u,定义V的分类如下：,X=x|d(u,x)是偶数，x V(G),Y=y|d(u,y)是奇数，y V(G),下面证明：对X中任意两点v与w,v与w不邻接！,27,设v与w是X中任意两个顶点。P是一条最短(u,v)路，而Q是一条最短的(u,w)路。,又设u1是P和Q的最后一个交点。由于P,Q是最短路，所以，P,Q中u到u1段长度相同，因此奇偶性相同。又P,Q的长均是偶数，所以，P,Q中u1v段和u1w段奇偶性相同。,如果v与w邻接，则可得到奇圈，矛盾！,28,作业,P29P30 13,14,20,22,29,Thank You!,
