第七章-图的着色3-图论及其应用课件.ppt

《第七章-图的着色3-图论及其应用课件.ppt》由会员分享，可在线阅读，更多相关《第七章-图的着色3-图论及其应用课件.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Email:图论及其应用图论及其应用任课教师：杨春任课教师：杨春1本次课主要内容本次课主要内容(一一)、与色数有关的几类图、与色数有关的几类图(二二)、完美图简介、完美图简介与色数有关的几类图和完美图与色数有关的几类图和完美图2 1、临界图、临界图(一一)、与色数有关的几类图、与色数有关的几类图 定义定义1 若对图若对图G的任意真子图的任意真子图H，都有，都有 ，则，则称称G是临界图。点色数为是临界图。点色数为k的临界图称为的临界图称为k临界图。临界图。3临界图临界图4临界图临界图非临界图非临界图 注：临界图由狄拉克在注：临界图由狄拉克在1952年首先提出并研究。上面年首先提出并研究。上面的的

2、4临界图是临界图是Grotzsch在在1958年提出的。年提出的。3 定理定理1 临界图有如下性质临界图有如下性质 (1)k色图均有色图均有k临界子图；临界子图；(2)每个临界图均为简单连通图；每个临界图均为简单连通图；(3)若若G是是k临界图，则临界图，则k-1k-1。证明：证明：(1)是显然的。是显然的。(2)因为删掉环或平行边中的一条边并不破坏原有的顶因为删掉环或平行边中的一条边并不破坏原有的顶点正常着色，所以每个临界图是单图；又因为删掉色数点正常着色，所以每个临界图是单图；又因为删掉色数较小的分支，剩下部分的图的色数和原图色数相等，所较小的分支，剩下部分的图的色数和原图色数相等，所以，

3、临界图必须是连通图。以，临界图必须是连通图。4 证明：设证明：设G的点色数为的点色数为 。由推论，。由推论，G中至少有中至少有 个顶点，其度数不小于个顶点，其度数不小于 所以，所以，即：，即：例例2 求证：临界图没有割点。求证：临界图没有割点。证明：设证明：设G是是k临界图。如果临界图。如果G有割点有割点v,设设G1,G2,Gr是是G-v的分支。又设第的分支。又设第i个分支顶点集为个分支顶点集为Vi(1ir)ir)。设设Hi=GViv,(1ir)。则。则Hi是是k-1可正常点着色可正常点着色的，现对每个的，现对每个Hi进行进行k-1正常点着色，且正常点着色，且v都分配同一种颜色，都分配同一种颜

4、色，那么，将着色后的那么，将着色后的Hi合在一起，得到合在一起，得到G的的k-1正常点着色方案，正常点着色方案，这与这与G是是k色图矛盾。所以临界图没有割点。色图矛盾。所以临界图没有割点。6 例例3 求证：仅有的求证：仅有的1临界图是临界图是k1;仅有的仅有的2临界图是临界图是K2;仅仅有的有的3临界图奇圈。临界图奇圈。证明：由于证明：由于1色图是空图，所以色图是空图，所以1临界图只能是临界图只能是K1;2色色图是偶图，所以，图是偶图，所以，2临界图只能是临界图只能是K2;3色图必然含有奇圈，色图必然含有奇圈，而奇圈的色数是而奇圈的色数是3，所以，所以，3临界图只能是奇圈。临界图只能是奇圈。例

5、例4 求证：布鲁克斯定理等价于下述命题：若求证：布鲁克斯定理等价于下述命题：若G是是k临临界图界图(k4),且不是完全且不是完全图图，则则2mn(k-1)+1,其中其中m为为G的的边边数而数而n为顶为顶点数。点数。证明：证明：(1)由布鲁克斯定理推例由布鲁克斯定理推例4中命题。中命题。因因G是是k临界图临界图,所以所以G是连通单图，又是连通单图，又k4,所以所以G不能不能是奇圈，再由是奇圈，再由G不是完全不是完全图图，所以由布，所以由布鲁鲁克斯定理有克斯定理有7 k。再由再由k临界图的性质，有临界图的性质，有k-1.k-1.所以：所以：(2)由例由例4中命题推布鲁克斯定理。中命题推布鲁克斯定理

6、。因为连通单图因为连通单图G不是奇圈，也不是完全图。设不是奇圈，也不是完全图。设G的的k临临界子图是界子图是H。情形情形1，H是奇圈。是奇圈。在这种情况下，由于在这种情况下，由于G不是奇圈，所以，不是奇圈，所以，H之外必然之外必然有边和有边和H相连，即相连，即(G)3,(G)3,另一方面，另一方面，k(G)=k(H)=3,k(G)=k(H)=3,所所8 即证明：即证明：2、唯一可着色图、唯一可着色图 对图的顶点进行正常着色，实际上给出图的顶点集合对图的顶点进行正常着色，实际上给出图的顶点集合的一种划分，不同的着色方案，给出的划分一般不同。的一种划分，不同的着色方案，给出的划分一般不同。但是，也

7、存在一类特殊图，对于任意的最优着色方案，但是，也存在一类特殊图，对于任意的最优着色方案，导出的顶点划分却是相同的。为此，我们给出如下定义。导出的顶点划分却是相同的。为此，我们给出如下定义。定义定义2 设简单标定图设简单标定图G的点色数是的点色数是k,如果在任意的如果在任意的k正正常点着色方案下，导出的顶点集合划分唯一，称常点着色方案下，导出的顶点集合划分唯一，称G是唯一是唯一k可着色图，简称唯一可着色图。可着色图，简称唯一可着色图。10 例例5 考察下面考察下面3色图是否是唯一色图是否是唯一3可着色图。可着色图。v3v2v1G1v1G2v5v4v3v2G3v5v4v3v2v1 解：解：(1)对

8、于对于G1来说，来说，G1的任意的任意3正常着色方案导出的正常着色方案导出的顶点划分均是顶点划分均是v1,v2v3，所以，所以，G1是唯是唯一一3可着色图；可着色图；11 下面给出唯一可着色图的几个特征。下面给出唯一可着色图的几个特征。定理定理2(哈拉里，哈拉里，1968）设设G是唯一是唯一k可着色图，可着色图，k2,则则：(1)k-1;k-1;(2)在在G G的任意一种的任意一种k k着色中，着色中，G G的任意两个色组的并的的任意两个色组的并的导出子图是连通的。导出子图是连通的。证明：证明：(1)若不然，设若不然，设 k-1,令令d(u)=,则uN(u)13 如果交换如果交换C1V(H1)

9、与与C2V(H1)中顶点颜色，得到中顶点颜色，得到G的的k着色着色1 1,显然，显然，与与1 1的色划分是不同的。这与的色划分是不同的。这与G G的着的着色唯一性矛盾。色唯一性矛盾。v1Gv5v4v3v2 例如，在下图例如，在下图G中，由黄色、红色色组导出的子图是中，由黄色、红色色组导出的子图是连通的。连通的。15 定理定理3(夏特朗）每个唯一夏特朗）每个唯一n(n2)可着色可着色图图是是(n-1)连连通的。通的。证明：设证明：设G是唯一是唯一n可着色图可着色图(n2)。情形情形1，如果，如果G是完全图，则是完全图，则G=Kn,显然显然G是是n-1连通的。连通的。情形情形2，如果，如果G是非完

10、全图，假若是非完全图，假若G不是不是(n-1)连通的，那连通的，那么其连通度么其连通度k(G)n-2n-2。于是。于是G G中存在点集中存在点集S S，S S=n-2,=n-2,使使得得G-SG-S不连通。不连通。设设是是G G的的n n着色方案。在该方案下，至少有两种颜色着色方案。在该方案下，至少有两种颜色c c1 1与与c c2 2，S S中的顶点都没有使用。中的顶点都没有使用。而由定理而由定理2的的(2),着着c1与与c2色的点导出子图必连通。所以色的点导出子图必连通。所以,着着c1与与c2色的顶点在色的顶点在G-S中的同一个分支中，设该分支为中的同一个分支中，设该分支为G1.16 定理

11、定理4 每个唯一每个唯一4可着色可平面图都是极大可平面图。可着色可平面图都是极大可平面图。证明：只需证明：证明：只需证明：m=3n-6即可。即可。一方面：一方面：G是可平面图，有：是可平面图，有：m3n-6;3n-6;另一方面：设另一方面：设G是唯一是唯一4可着色的可平面图，可着色的可平面图，是一种是一种4 4着色方案，色组记为着色方案，色组记为V Vi i(1i4).(1i4).因为因为ij时时，GViVVj j 是是连连通的，所以通的，所以:于是：于是：所以，所以，m=3n-6,即即G是极大可平面图。是极大可平面图。18 定义定义3 若图若图G的点色数是的点色数是k，且，且G中不含有三角形

12、，称中不含有三角形，称G是是一个不含三角形的一个不含三角形的k色图。色图。3、不含三角形的、不含三角形的k色图色图 例如：例如：不含三角形的三色图不含三角形的三色图不含三角形的不含三角形的4色图色图19 数学家狄拉克数学家狄拉克1953年在其论文年在其论文“k色图的构造色图的构造”中提出一中提出一个问题：对于任意大的一个正整数个问题：对于任意大的一个正整数k,是否存在一个图，不是否存在一个图，不包含三角形但色数是包含三角形但色数是k？上面问题分别由勃兰克上面问题分别由勃兰克.斯德卡兹斯德卡兹(1954),米歇尔斯基米歇尔斯基(1955)独立作出了回答。独立作出了回答。米歇尔斯基米歇尔斯基(19

13、55)给出了由一个不含三角形的给出了由一个不含三角形的k色图色图Gk构构造一个不含三角形的造一个不含三角形的k+1色图色图Gk+1的方法。的方法。构造方法：设构造方法：设Gk的顶点是的顶点是u1,u2,un,添加点添加点v1,v2,vn和点和点v。将将vi与与ui的所有邻点及的所有邻点及v相连，相连，1inin。如此得到的图就是一。如此得到的图就是一个不含三角形的个不含三角形的k+1k+1色图。色图。20 例例6，利用米歇尔斯基方法构造一个不含三角形的，利用米歇尔斯基方法构造一个不含三角形的4色图。色图。解：注意到解：注意到C5是不含三角形的是不含三角形的3色图，于是由色图，于是由C5可以构造

14、出可以构造出不含三角形的不含三角形的4色图。色图。不含三角形的不含三角形的3色图色图u4u3u2u1u5不含三角形的不含三角形的4色图色图u1u2u3u4u5v1v2v3v4v5v21 注：利用米歇尔斯基方法构造一个不含三角形的注：利用米歇尔斯基方法构造一个不含三角形的k色图时，色图时，结果图与初始图有关。结果图与初始图有关。例例7，设，设Gk是不含三角形的是不含三角形的k色图，顶点数为色图，顶点数为f(k),而而Gk+1是是由米歇尔斯基方法构造出来的不含三角形的由米歇尔斯基方法构造出来的不含三角形的k+1色图，其顶点色图，其顶点数设为数设为f(k+1)。求出。求出f(k)的递推公式。的递推公

15、式。解：解：定理定理5(米歇尔斯基米歇尔斯基)对于任意正整数对于任意正整数k,存在不含三角形的存在不含三角形的k色图。色图。1961年，数学家年，数学家Erdos用概率方法证明了更一般结论：用概率方法证明了更一般结论：定理定理6 (Erdos)对于任意正整数对于任意正整数m和和n,存在一个围长超过存在一个围长超过m的的n色图。色图。22 显然，图显然，图G的点色数与团数的关系为：的点色数与团数的关系为：定义定义5 设设G是一个图。若对是一个图。若对G的每个点导出子图的每个点导出子图H，均有，均有 ,则称则称G为完美图。为完美图。例如例如Kn,偶图是完美图，而不含三角形但含奇圈的图不偶图是完美图

16、，而不含三角形但含奇圈的图不是完美图。是完美图。因为不含三角形的但含奇圈的图的团数为因为不含三角形的但含奇圈的图的团数为2，但色数为，但色数为3，所以，它不能是完美图。，所以，它不能是完美图。注：完美图问题是点着色的进一步讨论题材，属于比较注：完美图问题是点着色的进一步讨论题材，属于比较高深和困难的问题。高深和困难的问题。24 图图G的点独立数记为的点独立数记为(G)(G)或或。定义定义6 设设G是一个图。由是一个图。由G中若干互不邻接的顶点作成中若干互不邻接的顶点作成的子集称为的子集称为G的一个点独立集；的一个点独立集；G中含顶点数最多的点独立中含顶点数最多的点独立集称为集称为G的最大独立集

17、，其包含的顶点数称为独立数。的最大独立集，其包含的顶点数称为独立数。对该问题的研究，早在对该问题的研究，早在1932年哥尼和加莱就已经涉及，年哥尼和加莱就已经涉及，但到了但到了1960年，完美图概念才被贝尔热正式提出。所以，年，完美图概念才被贝尔热正式提出。所以，贝尔热是完美图研究的代表人物。贝尔热是完美图研究的代表人物。注：关于图的覆盖与图的点独立数之间的关系，加莱得注：关于图的覆盖与图的点独立数之间的关系，加莱得到了一些很漂亮的结论。其中之一是：到了一些很漂亮的结论。其中之一是：25 定理定理7 偶图的补图是完美图。偶图的补图是完美图。分析：欲证分析：欲证 是完美图，要证明对任意是完美图，

18、要证明对任意 有有 由于由于 也是某偶图的补，所以只需要证明也是某偶图的补，所以只需要证明 补充定理：设补充定理：设G是一个偶图，记是一个偶图，记h为为G的最大匹配包含的的最大匹配包含的边数，边数，i为为G的最大独立集包含的顶点数，的最大独立集包含的顶点数，j为构成覆盖为构成覆盖G的的顶点的顶点的G的最小点边集合，则：的最小点边集合，则：i=j=m+n-h。2、关于色数的完美图的主要结论、关于色数的完美图的主要结论26 定义定义7 设设S是图是图G的顶点集合的一个划分。如果的顶点集合的一个划分。如果S的每个的每个子集在子集在G中的导出子图均是完全图，称中的导出子图均是完全图，称S是是G的一个完

19、全分的一个完全分类。类。G的最小完全分类所包含的元素个数称为的最小完全分类所包含的元素个数称为G的完全数，的完全数，记为记为(G),(G),即：即：3、关于独立数的完美图、关于独立数的完美图 注：注：。这是因为独立集中任意一点应该属。这是因为独立集中任意一点应该属于于S中的某个顶点子集，同时，中的某个顶点子集，同时，S中每个顶点子集最多包含中每个顶点子集最多包含独立集中的一个元素。独立集中的一个元素。28 定义定义8 若对若对G中每个点导出子图中每个点导出子图H，都有，都有称称G是关于点独立集的完美图。是关于点独立集的完美图。1960年，数学家贝尔热猜想：关于色数的完美图定义和年，数学家贝尔热

20、猜想：关于色数的完美图定义和关于独立集的完美图定义是等价的。即下面著名的完美图关于独立集的完美图定义是等价的。即下面著名的完美图定理。定理。1972年，年仅年，年仅22岁的罗瓦斯给出了上面定理的巧妙证明，岁的罗瓦斯给出了上面定理的巧妙证明，在图论与组合数学领域引起极大震惊。当时数学家富尔克森在图论与组合数学领域引起极大震惊。当时数学家富尔克森也在研究该定理，认为完美图定理条件太强，要修改。但当也在研究该定理，认为完美图定理条件太强，要修改。但当贝尔热告诉他罗瓦斯已经证明了定理时，他马上花几个小时贝尔热告诉他罗瓦斯已经证明了定理时，他马上花几个小时也完成了定理证明。也完成了定理证明。定理定理9(完美图定理完美图定理)G是关于色数的完美图当且仅当是关于色数的完美图当且仅当G是关于独立集的完美图。是关于独立集的完美图。29 作业作业 P187-190 习题习题7：22，23，24，2631Thank You!32