电子科技大学图论及其应用复习课件.

0.810.60.40.20xt00.511.5210.500.51n1图论及其应用复习课件0.810.60.40.20xt00.511.5210.500.51n2本次课主要内容(二)、重要结论期末复习(一)、重点概念(三)、应用0.810.60.40.20xt00.511.5210.500.51n3(一)、重点概念1、图、简单图、图的同构与自同构、度序列与图序列、补图与自补图、两个图的联图、两个图的积图、偶图；(1)图：一个图是一个序偶V,E，记为G=(V,E),其中：1)V是一个有限的非空集合，称为顶点集合,其元素称为顶点或点。用|V|表示顶点数；2)E是由V中的点组成的无序对构成的集合，称为边集，其元素称为边，且同一点对在E中可以重复出现多次。用|E|表示边数。(2)简单图：无环无重边的图称为简单图。0.810.60.40.20xt00.511.5210.500.51n4(3)图的度序列：一个图G的各个点的度d1,d2,…,dn构成的非负整数组(d1,d2,…,dn)称为G的度序列。注：度序列的判定问题是重点。(4)图的图序列：一个非负数组如果是某简单图的度序列，我们称它为可图序列，简称图序列。注：图序列的判定问题是重点。(5)图的同构：注：同构图个数是重点。0.810.60.40.20xt00.511.5210.500.51n5设有两个图G1=(V1,E1)和G2=(V2,E2),若在其顶点集合间存在双射，使得边之间存在如下关系：设u1↔u2v1↔v2,u1,v1V1,u2,v2V2;u1v1E1,当且仅当u2v2E2,且u1v1与u2v2的重数相同。称G1与G2同构，记为：12GG例1指出4个顶点的非同构的所有简单图。分析：四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进行枚举。0.810.60.40.20xt00.511.5210.500.51n6(6)补图与自补图1)对于一个简单图G=（V,E），令集合1,,EuvuvuvV则图H=（V，E1\E）称为G的补图，记为HG2)对于一个简单图G=（V,E），若，称G为自补图。GG注：要求掌握自补图的性质。0.810.60.40.20xt00.511.5210.500.51n7(7)偶图所谓具有二分类（X,Y）的偶图（或二部图）是指一个图，它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个端点在中，另一个端点在Y中.注:掌握偶图的判定。2、树、森林，生成树，最小生成树、根树、完全m元树。(1)树不含圈的图称为无圈图，树是连通的无圈图。(2)森林称无圈图G为森林。0.810.60.40.20xt00.511.5210.500.51n8(3)生成树图G的一个生成子图T如果是树，称它为G的一棵生成树；若T为森林，称它为G的一个生成森林。生成树的边称为树枝，G中非生成树的边称为弦。(4)最小生成树在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。注：要求熟练掌握最小生成树的求法。(5)根树一棵非平凡的有向树T，如果恰有一个顶点的入度为0，而其余所有顶点的入度为1，这样的的有向树称为根树。其中入度为0的点称为树根，出度为0的点称为树叶，入度为1，出度大于1的点称为内点。又将内点和树根统称为分支点。0.810.60.40.20xt00.511.5210.500.51n9(6)完全m元树对于根树T，若每个分支点至多m个儿子，称该根树为m元根树；若每个分支点恰有m个儿子，称它为完全m元树。注：对于完全m元树，要弄清其结构。3、途径(闭途径)，迹(闭迹),路(圈),最短路，连通图，连通分支，点连通度与边连通度。注：上面概念分别在1和3章(1)割边，割点和块(2)连通度0.810.60.40.20xt00.511.5210.500.51n10(1)欧拉图与欧拉环游(2)欧拉迹对于连通图G，如果G中存在经过每条边的闭迹，则称G为欧拉图，简称G为E图。欧拉闭迹又称为欧拉环游，或欧拉回路。对于连通图G，如果G中存在经过每条边的迹，则称该迹为G的一条欧拉迹。(3)哈密尔顿图与哈密尔顿圈如果经过图G的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。所经过的闭途径是G的一个生成圈，称为G的哈密尔顿圈。(4)哈密尔顿路图G的经过每个顶点的路称为哈密尔顿路。4、欧拉图，欧拉环游，欧拉迹，哈密尔顿圈，哈密尔顿图，哈密尔顿路，中国邮路问题，最优H圈。(5)中国邮递员问题；旅行售货员问题。0.810.60.40.20xt00.511.5210.500.51n115、匹配、最大匹配、完美匹配、最优匹配、因子分解。(1)匹配匹配M---如果M是图G的边子集(不含环），且M中的任意两条边没有共同顶点，则称M是G的一个匹配或对集或边独立集。(2)最大匹配与完美匹配最大匹配M---如果M是图G的包含边数最多的匹配，称M是G的一个最大匹配。特别是，若最大匹配饱和了G的所有顶点，称它为G的一个完美匹配。(3)最优匹配设G=(X,Y)是边赋权完全偶图，G中的一个权值最大的完美匹配称为G的最优匹配。0.810.60.40.20xt00.511.5210.500.51n12(4)因子分解所谓一个图G的因子分解，是指把图G分解为若干个边不重的因子之并。注：要弄清楚因子分解和完美匹配之间的联系与区别。6、平面图、极大平面图、极大外平面图、平面图的对偶图。(1)平面图：如果能把图G画在平面上，使得除顶点外，边与边之间没有交叉，称G可以嵌入平面，或称G是可平面图。可平面图G的边不交叉的一种画法，称为G的一种平面嵌入，G的平面嵌入表示的图称为平面图。0.810.60.40.20xt00.511.5210.500.51n13(2)极大平面图:设G是简单可平面图，如果G是Ki(1≦i≦4),或者在G的任意非邻接顶点间添加一条边后，得到的图均是非可平面图，则称G是极大可平面图。极大可平面图的平面嵌入称为极大平面图。(3)极大外平面图：若一个可平面图G存在一种平面嵌入，使得其所有顶点均在某个面的边界上，称该图为外可平面图。外可平面图的一种外平面嵌入，称为外平面图。(4)平面图的对偶图：给定平面图G，G的对偶图G*如下构造：1)在G的每个面fi内取一个点vi*作为G*的一个顶点；2)对G的一条边e,若e是面fi与fj的公共边，则连接vi*与vj*，且连线穿过边e;若e是面fi中的割边，则以vi为顶点作环，且让它与e相交。0.810.60.40.20xt00.511.5210.500.51n147、边色数、点色数、色多项式(1)、边色数设G是图，对G进行正常边着色需要的最少颜色数，称为G的边色数，记为：()G(2)、点色数对图G正常顶点着色需要的最少颜色数，称为图G的点色数。图G的点色数用表示。()G(3)、色多项式对图进行正常顶点着色，其方式数Pk(G)是k的多项式，称为图G的色多项式。0.810.60.40.20xt00.511.5210.500.51n158、强连通图、单向连通图、弱连通图(1)、强连通图(2)、弱连通图(3)、单向连通图若D的基础图是连通的，称D是弱连通图；若D的中任意两点是单向连通的，称D是单向连通图。若D的中任意两点是双向连通的，称D是强连通图；0.810.60.40.20xt00.511.5210.500.51n16(二)、重要结论1、握手定理及其推论定理1：图G=(V,E)中所有顶点的度的和等于边数m的2倍，即：()()2vVGdvm推论1在任何图中，奇点个数为偶数。推论2正则图的阶数和度数不同时为奇数。0.810.60.40.20xt00.511.5210.500.51n172、托兰定理定理2若n阶简单图G不包含Kl+1，则G度弱于某个完全l部图H，且若G具有与H相同的度序列，则:GH定理3设T是(n,m)树，则：3、树的性质1mn4、最小生成树算法5、偶图判定定理定理4图G是偶图当且仅当G中没有奇回路。0.810.60.40.20xt00.511.5210.500.51n18定理6下列陈述对于非平凡连通图G是等价的：(1)G是欧拉图；(2)G的顶点度数为偶数；(3)G的边集合能划分为圈。推论：连通非欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数。8、H图的判定定理7(必要条件)若G为H图，则对V(G)的任一非空顶点子集S，有：()GSS7、欧拉图、欧拉迹的判定0.810.60.40.20xt00.511.5210.500.51n19定理8(充分条件)对于n≧3的单图G，如果G中有：()2nG定理9(充分条件)对于n≧3的单图G，如果G中的任意两个不相邻顶点u与v，有：()()dudvn定理10(帮迪——闭包定理)图G是H图当且仅当它的闭包是H图。0.810.60.40.20xt00.511.5210.500.51n208、偶图匹配与因子分解定理13(Hall定理）设G=(X,Y)是偶图，则G存在饱和X每个顶点的匹配的充要条件是：,()(*)SXNSS对有推论：若G是k(k0)正则偶图，则G存在完美匹配。定理14(哥尼，1931)在偶图中，最大匹配的边数等于最小覆盖的顶点数。定理15K2n可一因子分解。0.810.60.40.20xt00.511.5210.500.51n21定理16具有H圈的三正则图可一因子分解。定理17K2n+1可2因子分解。定理18K2n可分解为一个1因子和n-1个2因子之和。定理19每个没有割边的3正则图是一个1因子和1个2因子之和。最优匹配算法(见教材）9、平面图及其对偶图1)、平面图的次数公式0.810.60.40.20xt00.511.5210.500.51n222)、平面图的欧拉公式定理20设G=(n,m)是平面图，则：deg()2ffm定理21(欧拉公式)设G=(n,m)是连通平面图，ф是G的面数，则：2nm3)、几个重要推论0.810.60.40.20xt00.511.5210.500.51n23推论1设G是具有n个点m条边ф个面的连通平面图，如果对G的每个面f,有：deg(f)≥l≥3,则：(2)2lmnl推论2设G是具有n个点m条边ф个面的简单平面图，则：36mn推论3设G是具有n个点m条边的简单平面图，则：5注：掌握证明方法。0.810.60.40.20xt00.511.5210.500.51n244)、对偶图的性质定理22平面图G的对偶图必然连通.5)、极大平面图的性质定理23设G是至少有3个顶点的平面图，则G是极大平面图，当且仅当G的每个面的次数是3且为单图。10、着色问题1)、边着色0.810.60.40.20xt00.511.5210.500.51n25定理24,()mnK定理25(哥尼，1916)若G是偶图，则()G定理26(维津定理，1964)若G是单图，则：()()+1GG或定理27设G是单图且Δ(G)0。若G中只有一个最大度点或恰有两个相邻的最大度点，则：()()GG0.810.60.40.20xt00.511.5210.500.51n26定理28设G是单图。若点数n=2k+1且边数mkΔ,则：()()1GG定理29设G是奇数阶Δ正则单图,若Δ0,则：()()1GG2)、点着色定理30对任意的图G，有：()()1GG0.810.60.40.20xt00.511.5210.500.51n27定理31(布鲁克斯，1941)若G是连通的单图，并且它既不是奇圈，又不是完全图，则：()()GG3)、色多项式定理32设G为简单图，则对任意有：()eEG()()()kkkPGPGePGe1)、递推计数法2)、理想子图计数方法0.810.60.40.20xt00.511.5210.500.51n