图论课件、子图的相关概念.ppt

《图论课件、子图的相关概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论及其应用应用数学学院1第一章图的基本概念本次课主要内容子图、图运算、路与连通性(一)、子图的相关概念(三)、路与连通性(二)、图运算21、子图简单地说，图G的任意一部分(包括本身)都称为是图G的的一个子图。定义1如果(一)、子图的相关概念且H中边的重数不超过G中对应边的条数，则称H为G的子图，记为当时，称H是G的真子图，记为32、点与边的导出子图(1)图G的顶点导出子图定义2如果，则以为顶点集，以两个端点均在中的边集组成的图，称为图G的点导出子图。记为：例1如图所示，求。其中12345图G4解：由点导出子图的定义得：135(2)图G的边导出子图定义3如果，则以为边集，以中边的所有端点为顶

2、点集组成的图，称为图G的边导出子图。记为：例2如图所示，求。其中5解：由边导出子图的定义得：12345图G1234563、图的生成子图定义3如果图G的一个子图包含G的所有顶点，称该子图为G的一个生成子图例2如图所示，求G的所有生成子图123图G解：按边数分别求出7定理：简单图G=(n,m)的所有生成子图个数为2m(二)、图运算在图论中，将两个或更多的图按照某种方式合并，或者对一个图作某种形式的操作，可以得到很有意义的新图。将图合并或对一个图进行操作，称为图运算。图运算形式很多。1、图的删点、删边运算(1)、图的删点运算设，在G中删去中的顶点和G中与之关联的所有边的操作，称为删点运算。记为特别

3、地，如果只删去一个点v，则记为G-v.8(2)、图的删边运算设，在G中删去中的所有边的操作，称为删边运算。记为特别地，如果只删去一条边e，则记为G-e.注：删点、删边后得到的图是原图的子图。2、图的并运算设G1,G2是G的两个子图，G1与G2并是指由为顶点集，以为边集组成的子图。记为：特别是，如果G1,G2不相交(没有公共顶点)，称它们的并为直接并，可以记为：92、图的交运算设G1,G2是G的两个子图，G1与G2交是指由为顶点集，以为边集组成的子图。记为：设G1,G2是两个图，G1与G2的差是指从G1中删去G2中的边得到的新图。记为G1-G2.3、图的差运算4、图的对称差运算(或环和运算)设

4、G1,G2是两个图，G1与G2的对称差定义为：10例3已知G1与G2，求1234abcdefG1h2354cdegijG2解：由相应运算定义得下面结果：1234abcdef5hgij234cde11123abfh2354gij1234abf5hgij125、图的联运算设G1,G2是两个不相交的图，作G1+G2，并且将G1中每个顶点和G2中的每个顶点连接，这样得到的新图称为G1与G2的联图。记为：例4已知G1与G2，求21G1345G2解：由联图的定义得：21345136、图的积图设是两个图。对点集的任意两个点u=(u1,u2)与v=(v1,v2),当(u1=v1和u2adjv2)或(u2=v

5、2和u1adjv1)时，把u与v相连。如此得到的新图称为G1与G2的积图。记为例5已知G1与G2，求G112G2345(1,4)(1,3)(1,5)(2,3)(2,4)(2,5)146、图的合成图设是两个图。对点集的任意两个点u=(u1,u2)与v=(v1,v2),当(u1adjv1)或(u1=v1和u2adjv2)时，把u与v相连。如此得到的新图称为G1与G2的合成图。记为例6已知G1与G2，求G112G2345(1,4)(1,3)(1,5)(2,3)(2,4)(2,5)15图的积运算是网络构造的常用方法。并行计算机中的网络拓扑常采用所谓的“超立方体”结构。采用该结构可使网络具有较好的可靠

6、性、较小的通信延迟和很好的可扩展性以及便于并行编程等优点。“超立方体”可以采用积图来递归构造。定义如下：(1)1方体(2)n方体定义为：Q1Q3Q2“超立方体”常采用下面简单的递归构造方法：16n方体Qn的顶点可用一个长度为n的二进制码来表示。Qn的顶点数目正好等于2n个。由n-1方体Qn-1构造Qn的方法是：将Qn-1拷贝一个。将原Qn-1每个顶点的码后再添加一个零，将拷贝得来的n-1方体每个顶点的码前面再添加一个1。然后在两个n-1方体之间连线：当且仅当两个顶点码只有一位对应位数字不同时，该两点连线。如此得到的图即为n方体。关于n方体Qn的性质研究，可以查阅到很多文献。经典文章是：Saa

7、dY,SchultzMH.Topologicalpropertiesofhypercubes[J].IEEETrans.Comput.1988,37(7):867--8727、图的联合把G1的一个顶点和G2的一个顶点粘合在一起后得到的新图称为G1与G2的联合。记为：17(三)、路与连通性对图的路与连通性进行研究，在计算机网络研究中有十分重要的意义。因为网络的抽象就是一个图。研究网络信息传递，信息寻径是主要问题