ppt25 图的顶点着色

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跟图的边着色问题一样，生活中的很多问题，也可以模型为所谓的图的顶点着色问题来处理。例如课程安排问题。(一)、相关概念课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论(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;0.810.60.40.20xt00.511.5210.500.51n4A10:GT,S。把课程模型为图G的顶点，两顶点连线当且仅当有某个学生同时选了这两门课程。GTMAGACLAS选课状态图0.810.60.40.20xt00.511.5210.500.51n5如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状态图中求所谓的点色数问题。GTMAGACLAS选课状态图0.810.60.40.20xt00.511.5210.500.51n6定义1设G是一个图，对G的每个顶点着色，使得相邻顶点着不同颜色，称为对G的正常顶点着色；如果用k种颜色可以对G进行正常顶点着色，称G可k正常顶点着色；对图G正常顶点着色需要的最少颜色数，称为图G的点色数。图G的点色数用表示。()G例1说明下图的点色数是4。GTMAGACLASGTMAGACLAS0.810.60.40.20xt00.511.5210.500.51n7解：一方面，由图的结构特征容易知道()4G另一方面，通过具体着色，用4种颜色可以得到该图的一种正常点着色，则：()4GGTMAGACLAS所以，()4G0.810.60.40.20xt00.511.5210.500.51n8注：对图的正常顶点着色，带来的是图的顶点集合的一种划分方式。所以，对应的实际问题也是分类问题。属于同一种颜色的顶点集合称为一个色组，它们彼此不相邻接，所以又称为点独立集。用点色数种颜色对图G正常着色，称为对图G的最优点着色。定义2色数为k的图称为k色图。(二)、图的点色数的几个结论定理1对任意的图G，有：()()1GG分析：事实上，定理结论容易想到，因为任意一个顶点度数至多为Δ，因此，正常着色过程中，其邻点最多用去Δ种颜色，所以，至少还有一种色可供该点正常着色使用。0.810.60.40.20xt00.511.5210.500.51n9证明：我们对顶点数作数学归纳证明。当n=1时，结论显然成立。设对顶点数少于n的图来说，定理结论成立。考虑一般的n阶图G。任取v∈V(G),令G1=G-v，由归纳假设：11()()1()1GGG设п是G1的一种Δ(G)+1正常点着色方案，因为v的邻点在п下至多用去Δ(G)种色，所以给v染上其邻点没有用过的色，就把п扩充成了G的Δ(G)+1着色方案。对于G来说，可以给出其Δ(G)+1正常点着色算法。0.810.60.40.20xt00.511.5210.500.51n10G的Δ(G)+1正常点着色算法设G=(V,E),V=｛v1,v2,…,vn｝,色集合C=｛1,2,…,Δ+1｝,着色方案为п。(1)令п(v1)=1,i=1;(2)若i=n,则停止；否则令：11()(),ijjiCvvjivv并且与相邻设k为C-C(vi+1)中的最小整数，令+1()=ivk(3)令i=i+1,转(2)。0.810.60.40.20xt00.511.5210.500.51n11例2给出下图的Δ+1正常点着色。v5v4v3v2v1v6解：色集C=｛1,2,3,4,5｝1(1),()=1v22(2),()=1,()2,3,4,5,2CvCCvk2(1),()=2v33(2),()=1,2,()3,4,5,3CvCCvk0.810.60.40.20xt00.511.5210.500.51n12v5v4v3v2v1v63(1),()=3v44(2),()=3,()1,2,4,5,1CvCCvk4(1),()=1v55(2),()=1,()2,3,4,5,2CvCCvk5(1),()=2v65(2),()=1,2,3,()4,5,4CvCCvk6(1),()=4vv5(2)v4(1)v3(3)v2(2)v1(1)v6(4)0.810.60.40.20xt00.511.5210.500.51n13v5v4v3v2v1v6注:(1)不能通过上面算法求出色数，例如，根据上面算法，我们求出了一个4色方案，但G是3色图：(2)Welsh—Powell稍微对上面算法做了一个修改，着色时按所谓最大度优先策略，即使用上面算法时，按顶点度数由大到小的次序着色。这样的着色方案起到了对上面算法的一个改进作用。0.810.60.40.20xt00.511.5210.500.51n14对于简单图G来说，数学家布鲁克斯(Brooks)给出了一个对定理1的色数改进界。这就是下面著名的布鲁克斯定理。定理2(布鲁克斯，1941)若G是连通的单图，并且它既不是奇圈，又不是完全图，则：()()GG数学家罗瓦斯在1973年给出了如下证明。证明：不失一般性，我们可以假设G是正则的，2连通的，最大度Δ≥3的简单图。原因如下：(1)容易证明：若G是非正则连通单图，最大度是Δ，则()()GG事实上，我们可以对G的顶点数作数学归纳证明：0.810.60.40.20xt00.511.5210.500.51n15当n=1时，结论显然成立；设对于阶数小于n的简单非正则连通单图来说，结论成立。下设G是阶数为n的非正则连通单图。设u是G中顶点，且d(u)=δΔ，考虑G1=G-u若G1是正则单图，则Δ(G1)=Δ(G)-1。于是G1是可Δ(G)顶点正常着色的，从而，G是可Δ(G)正常顶点着色的；若G1是非正则单图，则由数学归纳，G1是可Δ(G)顶点正常着色的，从而，G是可Δ(G)正常顶点着色的。(2)容易证明：若G是连通度为1的单图，最大度是Δ，则()()GG0.810.60.40.20xt00.511.5210.500.51n16(3)若Δ(G)≤2G只可能为K2或圈或路。因G不是奇圈，且不能为完全图，所以定理结论显然成立。所以，下面只需证明：假设G是正则的，2连通的，最大度Δ≥3的简单图，且不是完全图或奇圈，有：()()GG分两步完成证明。1)在上面条件下，我们证明：G中存在三点x1,x2,xn,使得G-｛x1,x2｝连通，x1与x2不邻接，但x1,x2与xn均邻接；x1x2xnG0.810.60.40.20xt00.511.5210.500.51n17情形1设G是3连通的正则非完全图。对于G中点xn,显然在其邻点中存在两个不邻接顶点x1与x2,使得G-｛x1,x2｝连通。情形2设G是连通度为2的正则非完全图。此时，存在点xn,使得G-xn连通且有割点v,于是G-xn至少含有两个块。vG-xn块块块0.810.60.40.20xt00.511.5210.500.51n18由于G本身2连通，所以G-xn的每个仅含有一个割点的块中均有点与xn邻接。设分属于H1与H2中的点x1与x2，它们与xn邻接。由于x1与x2分属于不同块，所以x1与x2不邻接。又显然G-｛x1,x2｝连通。2)对G中顶点进行如下排序：令xn-1∈V(G)-｛x1,x2,xn｝且与xn邻接；xn-2∈V(G)-｛x1,x2,xn，xn-1｝且与xn或xn-1邻接；xn-3∈V(G)-｛x1,x2,xn，xn-1,xn-2｝且与xn或xn-1或xn-2邻接；不断这样作下去，可得到G的顶点排序：x1,x2,…,xn0.810.60.40.20xt00.511.5210.500.51n19该顶点序列的特征是，对于1≦i≦n-1,xi与某个xi+k邻接。把着色算法用于G，按照上面顶点排序着色，容易知道，用Δ(G)种颜色可以完成G的正常点着色。对于简单图的点色数，还可以在定理2的基础上获得改进。定义3设G是至少有一条边的简单图，定义：2()()()()()maxmax()uVGvNudvduGdv其中N(u)为G中点u的邻域。称Δ2(G)为G的次大度。0.810.60.40.20xt00.511.5210.500.51n20如果令：2()(),()()()VGvvVGNvududv中存在点，满足那么，22()max()()GdvvVG例如：求下面图的次大度Δ2(G)G1G20.810.60.40.20xt00.511.5210.500.51n21解：(1)G1v5v4v3v2v1G2v5v4v3v2v1v8v7v6v9211()(),()()()VGvvVGNvududv中存在点，满足1234,,,vvvv22()max()()1GdvvVG(2)222()(),()()()VGvvVGNvududv中存在点，满足0.810.60.40.20xt00.511.5210.500.51n22G2v5v4v3v2v1v8v7v6v91235,869,,,,,vvvvvvv22()max()()3GdvvVG注：由次大度的定义知：Δ2(G)≦Δ(G)定理3设G是非空简单图，则：2()()1GG注：定理3是对定理2的一个改进！0.810.60.40.20xt00.511.5210.500.51n23G2v5v4v3v2v1v8v7v6v9例如：对下面单图来说，由定理2得：22()()5GG而由定理3得：222()()4GG推论：设G是非空简单图，若G中最大度点互不邻接，则有：()()GG0.810.60.40.20xt00.511.5210.500.51n241、四色定理(三)、四色与五色定理1852年，刚毕业于伦敦大学的格斯里(1831—1899)发现：给一张平面地图正常着色，至少需要4种颜色。这就是著名的4色定理。格斯里把他的证明通过他弟弟转交给著名数学家摩尔根，引起摩尔根极大兴趣，并于当天给数学家哈密尔顿写了封相关信件。但没有引起哈密尔顿的注意。直到1878年，在英国数学家会议上，数学家凯莱才再一次提到4色问题。0.810.60.40.20xt00.511.5210.500.51n251879年7月，业余数学家肯普(1849---1922）在英国自然杂志上宣称证明了4色定理。肯普是凯莱在剑桥大学的学生。1890年，英国数学家希伍德发表文章地图染色定理，通过构造反例，指出了肯普证明中的缺陷。后来，希伍德一直研究4色问题60年。泰特在此期间也研究4色问题，但其证明被托特否定。希伍德文章之后，4色问题研究进程开始走向停滞。到了20世纪，美国数学家比尔荷夫提出可约性概念，在此基础上，德国数学家海斯(1906—1995)认为，可以通过寻找所谓的不可约构形来证明4色定理。0.810.60.40.20xt00.511.5210.500.51n26Heesch估计不可约构形集合可能包含10000个元素，手工验证是不太可能。于是