图论30电子科大杨春

0.810.60.40.20xt00.511.5210.500.51n1Email:[e-mail]图论及其应用任课教师：杨春数学科学学院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)联图设G1,G2是两个不相交的图，作G1+G2，并且将G1中每个顶点和G2中的每个顶点连接，这样得到的新图称为G1与G2的联图。记为：12GG(8)积图设是两个图。对点集111222(,),(,),GVEGVE12VVV的任意两个点u=(u1,u2)与v=(v1,v2),当(u1=v1和u2adjv2)或(u2=v2和u1adjv1)时，把u与v相连。如此得到的新图称为G1与G2的积图。记为12GGG0.810.60.40.20xt00.511.5210.500.51n8(9)偶图所谓具有二分类（X,Y）的偶图（或二部图）是指一个图，它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个端点在中，另一个端点在Y中.注:掌握偶图的判定。2、树、森林，生成树，最小生成树、根树、完全m元树。(1)树不含圈的图称为无圈图，树是连通的无圈图。(2)森林称无圈图G为森林。0.810.60.40.20xt00.511.5210.500.51n9(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.51n10(6)完全m元树对于根树T，若每个分支点至多m个儿子，称该根树为m元根树；若每个分支点恰有m个儿子，称它为完全m元树。注：对于完全m元树，要弄清其结构。3、途径(闭途径)，迹(闭迹),路(圈),最短路，连通图，连通分支，点连通度与边连通度。注：上面概念分别在1和3章4、欧拉图，欧拉环游，欧拉迹，哈密尔顿圈，哈密尔顿图，哈密尔顿路，中国邮路问题，最优H圈。0.810.60.40.20xt00.511.5210.500.51n11(1)欧拉图与欧拉环游(2)欧拉迹对于连通图G，如果G中存在经过每条边的闭迹，则称G为欧拉图，简称G为E图。欧拉闭迹又称为欧拉环游，或欧拉回路。对于连通图G，如果G中存在经过每条边的迹，则称该迹为G的一条欧拉迹。(3)哈密尔顿图与哈密尔顿圈如果经过图G的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。所经过的闭途径是G的一个生成圈，称为G的哈密尔顿圈。(4)哈密尔顿路图G的经过每个顶点的路称为哈密尔顿路。0.810.60.40.20xt00.511.5210.500.51n125、匹配、最大匹配、完美匹配、最优匹配、因子分解。(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.51n13(4)因子分解所谓一个图G的因子分解，是指把图G分解为若干个边不重的因子之并。注：要弄清楚因子分解和完美匹配之间的联系与区别。6、平面图、极大平面图、极大外平面图、平面图的对偶图。(1)平面图：如果能把图G画在平面上，使得除顶点外，边与边之间没有交叉，称G可以嵌入平面，或称G是可平面图。可平面图G的边不交叉的一种画法，称为G的一种平面嵌入，G的平面嵌入表示的图称为平面图。0.810.60.40.20xt00.511.5210.500.51n14(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.51n157、边色数、点色数、色多项式(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.51n168、强连通图、单向连通图、弱连通图(1)、强连通图(2)、弱连通图(3)、单向连通图若D的基础图是连通的，称D是弱连通图；若D的中任意两点是单向连通的，称D是单向连通图。若D的中任意两点是双向连通的，称D是强连通图；0.810.60.40.20xt00.511.5210.500.51n17(二)、重要结论1、握手定理及其推论定理1：图G=(V,E)中所有顶点的度的和等于边数m的2倍，即：()()2vVGdvm推论1在任何图中，奇点个数为偶数。推论2正则图的阶数和度数不同时为奇数。0.810.60.40.20xt00.511.5210.500.51n182、托兰定理定理2若n阶简单图G不包含Kl+1，则G度弱于某个完全l部图H，且若G具有与H相同的度序列，则:GH定理3设T是(n,m)树，则：3、树的性质1mn4、最小生成树算法0.810.60.40.20xt00.511.5210.500.51n195、偶图判定定理定理4图G是偶图当且仅当G中没有奇回路。6、敏格尔定理定理5(1)设x与y是图G中的两个不相邻点，则G中分离点x与y的最小点数等于独立的(x,y)路的最大数目；(2)设x与y是图G中的两个不相邻点，则G中分离点x与y的最小边数等于G中边不重的(x,y)路的最大数目。7、欧拉图、欧拉迹的判定0.810.60.40.20xt00.511.5210.500.51n20定理6下列陈述对于非平凡连通图G是等价的：(1)G是欧拉图；(2)G的顶点度数为偶数；(3)G的边集合能划分为圈。推论：连通非欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数。8、H图的判定定理7(必要条件)若G为H图，则对V(G)的任一非空顶点子集S，有：()GSS0.810.60.40.20xt00.511.5210.500.51n21定理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.51n22定理11(Chvátal——度序列判定法)设简单图G的度序列是(d1,d2,…,dn),这里，d1≦d2≦…≦dn,并且n≧3.若对任意的mn/2,或者dmm,或者dn-m≧n-m,则G是H图。定理12设G是n阶单图。若n≧3且1()12nEG则G是H图；并且，具有n个顶点条边的非H图只有C1,n以及C2,5.112n0.810.60.40.20xt00.511.5210.500.51n238、偶图匹配与因子分解定理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.51n24定理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.51n252)、平面图的欧拉公式定理20设G=(n,m)是平面图，则：deg()2ffm定理21(欧拉公式)设G=(n,m)是连通平面图，ф是G的面数，则：2nm3)、几个重要推论0.810.60.40.20xt00.511.5210.500.51n26推论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.51n27注：掌握证明方法。4)、对偶