图论30电子科大杨春.pptx

该【图论30电子科大杨春 】是由【小屁孩】上传分享，文档一共【48】页，该文档可以免费在线阅读，需要了解更多关于【图论30电子科大杨春 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。Email:yc517922@图论及其应用任课教师:杨春数学科学学院12021/10/10本次课主要内容(二)、重要结论期末复****一)、重点概念(三)、应用22021/10/10(一)、重点概念1、图、简单图、图的同构与自同构、度序列与图序列、补图与自补图、两个图的联图、两个图的积图、偶图;(1)图:一个图是一个序偶<V,E>,记为G=(V,E),其中:1)V是一个有限的非空集合,称为顶点集合,其元素称为顶点或点。用|V|表示顶点数;2)E是由V中的点组成的无序对构成的集合,称为边集,其元素称为边,且同一点对在E中可以重复出现多次。用|E|表示边数。(2)简单图:无环无重边的图称为简单图。32021/10/10(3)图的度序列:一个图G的各个点的度d1,d2,…,dn构成的非负整数组(d1,d2,…,dn)称为G的度序列。注:度序列的判定问题是重点。(4)图的图序列:一个非负数组如果是某简单图的度序列,我们称它为可图序列,简称图序列。注:度序列的判定问题是重点。(5)图的同构:42021/10/10设有两个图G1=(V1,E1)和G2=(V2,E2),若在其顶点集合间存在双射,使得边之间存在如下关系:设u1?u2v1?v2,u1,v1V1,u2,v2V2;u1v1E1,当且仅当u2v2E2,且u1v1与u2v2的重数相同。称G1与G2同构,记为:例1指出4个顶点的非同构的所有简单图。分析:四个顶点的简单图最少边数为0,最多边数为6,所以可按边数进行枚举。52021/10/10(6)补图与自补图1)对于一个简单图G=(V,E),令集合则图H=(V,E1\E)称为G的补图,记为2)对于一个简单图G=(V,E),若,称G为自补图。注:要求掌握自补图的性质。62021/10/10(7)联图设G1,G2是两个不相交的图,作G1+G2,并且将G1中每个顶点和G2中的每个顶点连接,这样得到的新图称为G1与G2的联图。记为:(8)积图设是两个图。对点集的任意两个点u=(u1,u2)与v=(v1,v2),当(u1=v1和u2adjv2)或(u2=v2和u1adjv1)时,把u与v相连。如此得到的新图称为G1与G2的积图。记为72021/10/10(9)偶图所谓具有二分类(X,Y)的偶图(或二部图)是指一个图,它的点集可以分解为两个(非空)子集X和Y,使得每条边的一个端点在中,:掌握偶图的判定。2、树、森林,生成树,最小生成树、根树、完全m元树。(1)树不含圈的图称为无圈图,树是连通的无圈图。(2)森林称无圈图G为森林。82021/10/10(3)生成树图G的一个生成子图T如果是树,称它为G的一棵生成树;若T为森林,称它为G的一个生成森林。生成树的边称为树枝,G中非生成树的边称为弦。(4)最小生成树在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。注:要求熟练掌握最小生成树的求法。(5)根树一棵非平凡的有向树T,如果恰有一个顶点的入度为0,而其余所有顶点的入度为1,这样的的有向树称为根树。其中入度为0的点称为树根,出度为0的点称为树叶,入度为1,出度大于1的点称为内点。又将内点和树根统称为分支点。92021/10/10(6)完全m元树对于根树T,若每个分支点至多m个儿子,称该根树为m元根树;若每个分支点恰有m个儿子,称它为完全m元树。注:对于完全m元树,要弄清其结构。3、途径(闭途径),迹(闭迹),路(圈),最短路,连通图,连通分支,点连通度与边连通度。注:上面概念分别在1和3章4、欧拉图,欧拉环游,欧拉迹,哈密尔顿圈,哈密尔顿图,哈密尔顿路,中国邮路问题,最优H圈。102021/10/10