资源描述:
《《期末复习》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、图论及其应用复习课件数学科学学院1本次课主要内容(二)、重要结论期末复习(一)、重点概念(三)、应用2(一)、重点概念1、图、简单图、图的同构与自同构、度序列与图序列、补图与自补图、两个图的联图、两个图的积图、偶图;(1)图:一个图是一个序偶,记为G=(V,E),其中:1)V是一个有限的非空集合,称为顶点集合,其元素称为顶点或点。用
2、V
3、表示顶点数;2)E是由V中的点组成的无序对构成的集合,称为边集,其元素称为边,且同一点对在E中可以重复出现多次。用
4、E
5、表示边数。(2)简单图:无环无重边的图称为简
6、单图。3(3)图的度序列:一个图G的各个点的度d1,d2,…,dn构成的非负整数组(d1,d2,…,dn)称为G的度序列。注:度序列的判定问题是重点。(4)图的图序列:一个非负数组如果是某简单图的度序列,我们称它为可图序列,简称图序列。注:度序列的判定问题是重点。(5)图的同构:4设有两个图G1=(V1,E1)和G2=(V2,E2),若在其顶点集合间存在双射,使得边之间存在如下关系:设u1↔u2v1↔v2,u1,v1V1,u2,v2V2;u1v1E1,当且仅当u2v2E2,且u1v1与u2v2的重数相同。称G
7、1与G2同构,记为:例1指出4个顶点的非同构的所有简单图。分析:四个顶点的简单图最少边数为0,最多边数为6,所以可按边数进行枚举。5(6)补图与自补图1)对于一个简单图G=(V,E),令集合则图H=(V,E1E)称为G的补图,记为2)对于一个简单图G=(V,E),若,称G为自补图。注:要求掌握自补图的性质。6(7)联图设G1,G2是两个不相交的图,作G1+G2,并且将G1中每个顶点和G2中的每个顶点连接,这样得到的新图称为G1与G2的联图。记为:(8)积图设是两个图。对点集的任意两个点u=(u1,u2)与v
8、=(v1,v2),当(u1=v1和u2adjv2)或(u2=v2和u1adjv1)时,把u与v相连。如此得到的新图称为G1与G2的积图。记为7(9)偶图所谓具有二分类(X,Y)的偶图(或二部图)是指一个图,它的点集可以分解为两个(非空)子集X和Y,使得每条边的一个端点在中,另一个端点在Y中.注:掌握偶图的判定。2、树、森林,生成树,最小生成树、根树、完全m元树。(1)树不含圈的图称为无圈图,树是连通的无圈图。(2)森林称无圈图G为森林。8(3)生成树图G的一个生成子图T如果是树,称它为G的一棵生成树;若T为森
9、林,称它为G的一个生成森林。生成树的边称为树枝,G中非生成树的边称为弦。(4)最小生成树在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。注:要求熟练掌握最小生成树的求法。(5)根树一棵非平凡的有向树T,如果恰有一个顶点的入度为0,而其余所有顶点的入度为1,这样的的有向树称为根树。其中入度为0的点称为树根,出度为0的点称为树叶,入度为1,出度大于1的点称为内点。又将内点和树根统称为分支点。9(6)完全m元树对于根树T,若每个分支点至多m个儿子,称该根树为m元根树;若每个分支点恰有
10、m个儿子,称它为完全m元树。注:对于完全m元树,要弄清其结构。3、途径(闭途径),迹(闭迹),路(圈),最短路,连通图,连通分支,点连通度与边连通度。注:上面概念分别在1和3章4、欧拉图,欧拉环游,欧拉迹,哈密尔顿圈,哈密尔顿图,哈密尔顿路,中国邮路问题,最优H圈。10(1)欧拉图与欧拉环游(2)欧拉迹对于连通图G,如果G中存在经过每条边的闭迹,则称G为欧拉图,简称G为E图。欧拉闭迹又称为欧拉环游,或欧拉回路。对于连通图G,如果G中存在经过每条边的迹,则称该迹为G的一条欧拉迹。(3)哈密尔顿图与哈密尔顿圈如果
11、经过图G的每个顶点恰好一次后能够回到出发点,称这样的图为哈密尔顿图,简称H图。所经过的闭途径是G的一个生成圈,称为G的哈密尔顿圈。(4)哈密尔顿路图G的经过每个顶点的路称为哈密尔顿路。115、匹配、最大匹配、完美匹配、最优匹配、因子分解。(1)匹配匹配M---如果M是图G的边子集(不含环),且M中的任意两条边没有共同顶点,则称M是G的一个匹配或对集或边独立集。(2)最大匹配与完美匹配最大匹配M---如果M是图G的包含边数最多的匹配,称M是G的一个最大匹配。特别是,若最大匹配饱和了G的所有顶点,称它为G的一个完
12、美匹配。(3)最优匹配设G=(X,Y)是边赋权完全偶图,G中的一个权值最大的完美匹配称为G的最优匹配。12(4)因子分解所谓一个图G的因子分解,是指把图G分解为若干个边不重的因子之并。注:要弄清楚因子分解和完美匹配之间的联系与区别。6、平面图、极大平面图、极大外平面图、平面图的对偶图。(1)平面图:如果能把图G画在平面上,使得除顶点外,边与边之间没有交叉,称G可以嵌入平面,或称G是可平面图。可平面图