图论电子科大杨春5

Email:yc517922@126.com

图论及其应用任课教师：杨春数学科学学院1本次课主要内容(二)、重要结论期末复习(一)、重点概念(三)、应用2

(一)、重点概念1、图、简单图、图的同构与自同构、度序列与图序列、补图与自补图、两个图的联图、两个图的积图、偶图；(1)图：一个图是一个序偶<V,E>，记为G=(V,E),其中：1)V是一个有限的非空集合，称为顶点集合,其元素称为顶点或点。用|V|表示顶点数；2)E是由V中的点组成的无序对构成的集合，称为边集，其元素称为边，且同一点对在E中可以重复出现多次。用|E|表示边数。(2)简单图：无环无重边的图称为简单图。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的重数相同。称G1与G2同构，记为：例1指出4个顶点的非同构的所有简单图。分析：四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进行枚举。5(6)补图与自补图1)对于一个简单图G=（V,E），令集合则图H=（V，E1\E）称为G的补图，记为2)对于一个简单图G=（V,E），若，称G为自补图。注：要求掌握自补图的性质。6(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的积图。记为7(9)偶图

所谓具有二分类（X,Y）的偶图（或二部图）是指一个图，它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个端点在中，另一个端点在Y中.注:掌握偶图的判定。2、树、森林，生成树，最小生成树、根树、完全m元树。(1)树

不含圈的图称为无圈图，树是连通的无圈图。(2)森林

称无圈图G为森林。8(3)生成树图G的一个生成子图T如果是树，称它为G的一棵生成树；若T为森林，称它为G的一个生成森林。生成树的边称为树枝，G中非生成树的边称为弦。(4)最小生成树

在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。

注：要求熟练掌握最小生成树的求法。(5)根树一棵非平凡的有向树T，如果恰有一个顶点的入度为0，而其余所有顶点的入度为1，这样的的有向树称为根树。其中入度为0的点称为树根，出度为0的点称为树叶，入度为1，出度大于1的点称为内点。又将内点和树根统称为分支点。9(6)完全m元树对于根树T，若每个分支点至多m个儿子，称该根树为m元根树；若每个分支点恰有m个儿子，称它为完全m元树。注：对于完全m元树，要弄清其结构。3、途径(闭途径)，迹(闭迹),路(圈),最短路，连通图，连通分支，点连通度与边连通度。注：上面概念分别在1和3章4、欧拉图，欧拉环游，欧拉迹，哈密尔顿圈，哈密尔顿图，哈密尔顿路，中国邮路问题，最优H圈。10(1)欧拉拉图图与与欧欧拉拉环环游游(2)欧拉拉迹迹对于于连连通通图图G，如如果果G中存存在在经经过过每每条条边边的的闭闭迹迹，，则则称称G为欧欧拉拉图图，，简简称称G为E图。。欧欧拉拉闭闭迹迹又又称称为为欧欧拉拉环环游游，，或或欧欧拉拉回回路路。。对于于连连通通图图G，如如果果G中存存在在经经过过每每条条边边的的迹迹，，则则称称该该迹迹为为G的一一条条欧欧拉拉迹迹。。(3)哈密密尔尔顿顿图图与与哈哈密密尔尔顿顿圈圈如果果经经过过图图G的每每个个顶顶点点恰恰好好一一次次后后能能够够回回到到出出发发点点，，称称这这样样的的图图为为哈哈密密尔尔顿顿图图，，简简称称H图。。所所经经过过的的闭闭途途径径是是G的一一个个生生成成圈圈，，称称为为G的哈哈密密尔尔顿顿圈圈。。(4)哈密密尔尔顿顿路路图G的经经过过每每个个顶顶点点的的路路称称为为哈哈密密尔尔顿顿路路。。115、匹匹配配、、最最大大匹匹配配、、完完美美匹匹配配、、最最优优匹匹配配、、因因子子分分解解。。(1)匹配配匹配配M---如果果M是图图G的边边子子集集(不含含环环）），，且且M中的的任任意意两两条条边边没没有有共共同同顶顶点点，，则则称称M是G的一一个个匹匹配配或或对对集集或或边边独独立立集集。。(2)最大大匹匹配配与与完完美美匹匹配配最大大匹匹配配M---如果果M是图图G的包包含含边边数数最最多多的的匹匹配配，，称称M是G的一一个个最最大大匹匹配配。。特特别别是是，，若若最最大大匹匹配配饱饱和和了了G的所所有有顶顶点点，，称称它它为为G的一一个个完完美美匹匹配配。。(3)最优优匹匹配配设G=(X,Y)是边边赋赋权权完完全全偶偶图图，，G中的的一一个个权权值值最最大大的的完完美美匹匹配配称称为为G的最最优优匹匹配配。。12(4)因子子分分解解所谓谓一一个个图图G的因因子子分分解解，，是是指指把把图图G分解解为为若若干干个个边边不不重重的的因因子子之之并并。。注：：要要弄弄清清楚楚因因子子分分解解和和完完美美匹匹配配之之间间的的联联系系与与区区别别。。6、平平面面图图、、极极大大平平面面图图、、极极大大外外平平面面图图、、平平面面图图的的对对偶偶图图。。(1)平面面图图：：如如果果能能把把图图G画在在平平面面上上，，使使得得除除顶顶点点外外，，边边与与边边之之间间没没有有交交叉叉，，称称G可以以嵌嵌入入平平面面，，或或称称G是可可平平面面图图。。可可平平面面图图G的边边不不交交叉叉的的一一种种画画法法，，称称为为G的一一种种平平面面嵌嵌入入，，G的平平面面嵌嵌入入表表示示的的图图称称为为平平面面图图。。13(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相交。147、边色数、点点色数、色多多项式(1)、边色数设G是图，对G进行正常边着着色需要的最最少颜色数，，称为G的边色数，记记为：(2)、点色数对图G正常顶点着色色需要的最少少颜色数，称称为图G的点色数。图图G的点色数用表表示。(3)、色多项式对图进行正常常顶点着色，，其方式数Pk(G)是k的多项式，称称为图G的色多项式。。158、强连通图、、单向连通图图、弱连通图图(1)、强连通图(2)、弱连通图(3)、单向连通图图若D的基础图是连连通的，称D是弱连通图；；若D的中任意两点点是单向连通通的，称D是单向连通图图。若D的中任意两点点是双向连通通的，称D是强连通图；；16(二)、重要结论1、握手定理及及其推论定理1：图G=(V,E)中所有顶点的的度的和等于于边数m的2倍，即：推论1在任何图中，，奇点个数为为偶数。推论2正则图的阶数数和度数不同同时为奇数。。172、托兰定理定理2若n阶简单图G不包含Kl+1，则G度弱于某个完完全l部图H，且若G具有与H相同的度序列列，则:定理3设T是(n,m)树，则：3、树的性质4、最小生成树树算法185、偶图判定定定理定理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、欧拉图、欧欧拉迹的判定定19定理6下列陈述对于于非平凡连通通图G是等价的：(1)G是欧拉图；(2)G的顶点度数为为偶数；(3)G的边集合能划划分为圈。推论：连通通非欧拉图G存在欧拉迹当当且仅当G中只有两个顶顶点度数为奇奇数。8、H图的判定定理7(必要条件)若G为H图，则对V(G)的任一非空顶顶点子集S，有：20定理8(充分条件)对于n≧3的单图G，如果G中有：定理9(充分条件)对于n≧3的单图G，如果G中的任意两个个不相邻顶点点u与v，有：定理10(帮迪——闭包定理)图G是H图当且仅当它它的闭包是H图。21定理11(Chvátal———度序列判定法法)设简单图G的度序列是(d1,d2,…,dn),这里，d1≦d2≦…≦dn,并且n≧3.若对任意的m<n/2,或者dm>m,或者dn-m≧n-m,则G是H图。定理12设G是n阶单图。若n≧3且则G是H图；并且，具具有n个顶点条条边的非H图只有C1,n以及C2,5.228、偶图匹配与与因子分解定理13(Hall定理）设G=(X,Y)是偶图，则G存在饱和X每个顶点的匹匹配的充要条条件是：推论：若G是k(k>0)正则偶图，则则G存在完美匹配配。定理14(哥尼，1931)在偶图中，最最大匹配的边边数等于最小小覆盖的顶点点数。定理15K2n可一因子分解解。23定理16具有H圈的三正则图图可一因子分分解。定理17K2n+1可2因子分解。定理18K2n可分解为一个个1因子和n-1个2因子之和。定理19每个没有割边边的3正则图是一个个1因子和1个2因子之和。最优匹配算法法(见教材）9、平面图及其其对偶图1)、平面图的次次数公式242)、平面图的欧欧拉公式定理20设G=(n,m)是平面图，则则：定理21(欧拉公式)设G=(n,m)是连通平面图图，ф是G的面数，则：：3)、几个重要推推论25推论1设G是具有n个点m条边ф个面的连通平平面图，如果果对G的每个面f,有：deg(f)≥l≥3,则：推论2设G是具有n个点m条边ф个面的的简单单平面面图，，则：：推论3设G是具有有n个点m条边的的简单单平面面图，，则：：26注：掌掌握证证明方方法。。4)、对偶偶图的的性质质定理22平面图图G的对偶偶图必必然连连通.5)、极大大平面面图的的性质质定理23设G是至少少有3个顶点点的平平面图图，则则G是极大大平面面图，，当且且仅当当G的每个个面的的次数数是3且为单单图。。10、着色色问题题1)、边着着色27定理24定理25(哥尼，，1916)若G是偶图图，则则定理26(维津定定理，，1964)若G是单图图，则则：定理27设G是单图图且Δ(G)>0。若G中只有有一个个最大大度点点或恰恰有两两个相相邻的的最大大度点点，则则：28定理28设G是单图图。若若点数数n=2k+1且边数数m>kΔ,则：定理29设G是奇数数阶Δ正则单图,若Δ>0,则：2)、点着着色定理30对任意意的图图G，有：：29定理31(布鲁克克斯，，1941)若G是连通通的单单图，，并且且它既既不是是奇圈圈，又又不是是完全全图，，则：：3)、色多多项式式定理32设G为简单单图，，则对对任意意有有：1)、递推推计数数法2)、理想想子图图计数数方法法30(1)画出G的补图图(2)求出关关于补补图的的(3)写出关关于补补图的的伴随随多项项式(4)将代代入伴伴随多多项式式中得得到Pk(G)。11、根树树问题题定理32在完全全m元树T中，若若树叶叶数为为t,分支点点数为为i,则：31(三)、图论论应用用1、偶偶图图匹配配问题题例1有7名研究究生A,B,C,D,E,F,G毕业寻寻找工工作。。就业业处提提供的的公开开职位位是：：会计计师(a),咨询师师(b),编辑(c),程序员员(d),记者(e),秘书(f)和教师师(g)。每名名学生生申请请的职职位如如下：：A:b,c;B:a,b,d,f,g;C:b,e;D:b,c,e;E:a,c,d,f;F:c,e;G:d,e,f,g;问：学学生能能找到到理想想工作作吗？？重点掌掌握如如下两两方面面应用用32问题转转化为为是否否有饱饱和X每个顶顶点的的一个个匹配配。FEDCBAGabcdefg解：如如果令令X=｛A,B,C,D,E,F,G｝,Y=｛a,b,c,d,e,f,g｝,X中顶点点与Y中顶点点连线线当且且仅当当学生生申请请了该该工作作。于于是，，得到到反映映学生生和职职位之之间的的状态态图：：33当S取X中四元元点集集时，，若取取S=｛A,C,D,F｝,则有3=|N(S)|<|S|=4所以，，不存存在饱饱和X每个顶顶点的的匹配配。2、着着色色问题题1)、边边着着色问问题例2(排课表表问题题)在一个个学校校中，，有7个教师师12个班级级。在在每周周5天教学学日条条件下下，教教课的的要求求由如如下矩矩阵给给出：：34x1x2x3x4x6x5x7y2y1y8y7y6y5y4y3y10y9y11y12其中，pij表示xi必须教yj班的节数。求求：(1)一天分成几节节课，才能满满足所提出的的要求？(2)若安排出每天天8节课的时间表表，需要多少少间教室？35x1x2x3x4x6x5x7y2y1y8y7y6y5y4y3y10y9y11y12解：问题可模模型为一个偶偶图。一节课对应边边正常着色的的一个色组。。由于G是偶图，所以以边色数为G的最大度35。这样，最少少总课时为35节课。平均每每天要安排7节课。如果每天安排排8节课，因为G的总边数为240，所以需要的的教室数为240/40=6。36例3(比赛安排问题题)Alvin(A)曾邀请3对夫妇到他的的避暑别墅住住一个星期。。他们是：Bob和Carrie,David和Edith,Frank和Gena。由于这6人都喜欢网球球运动，所以以他们决定进进行网球比赛赛。6位客人的每一一位都要和其其配偶之外的的每位客人比比赛。另外，，Alvin将分别和David，Edith，Frank，Gena进行一场比赛赛。若没有人人在同一天进进行2场比赛，则要要在最少天数数完成比赛，，如何安排？？解：用点表示示参赛人，两两点连线当且且仅当两人有有比赛。这样样得到比赛状状态图。问题对应于求求状态图的一一种最优边着着色(用最少色数进进行正常边着着色)。37状态图为：FDAGCEB图G由于n=2×3+1,所以k=3。而Δ=5，m=16>3×5=kΔ,所以由定理5知：38最优着色为：：FDAGCEB图G39例4课程安排问题题：某大学数数学系要为这这个夏季安排排课程表。所所要开设的课课程为：图论论(GT),统计学(S),线性代数(LA),高等微积分(AC),几何学(G),和近世代数(MA)。现有10名学生(如下所示)需要选修这些些课程。根据据这些信息，，确定开设这这些课程所需需要的最少时时间段数，使使得学生选课课不会发生冲冲突。(学生用Ai表示）A1:LA,S;A2:MA,LA,G;A3:MA,G,LA;A4:G,LA,AC;A5:AC,LA,S;A6:G,AC;A7:GT,MA,LA;A8:LA,GT,S;A9:AC,S,LA;2)、点