图论及其应用(24)课件.ppt

1,本次课主要内容,(一)、相关概念,(二)、图的点色数的几个结论,(三)、四色与五色定理,图的顶点着色,(四)、顶点着色的应用,1本次课主要内容(一)、相关概念(二)、图的点色数的几个结论,2,跟图的边着色问题一样，生活中的很多问题，也可以模型为所谓的图的顶点着色问题来处理。例如课程安排问题。,(一)、相关概念,课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论(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 跟图的边着色问题一样，生活中的很多问题，也可以模,3,A10: GT, S。,把课程模型为图G的顶点，两顶点连线当且仅当有某个学生同时选了这两门课程。,3 A10: GT, S。 把课程模型为图G,4,如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状态图中求所谓的点色数问题。,4 如果我们用同一颜色给同一时段的课程顶点染色，那么,5,定义1 设G是一个图，对G的每个顶点着色，使得相邻顶点着不同颜色，称为对G的正常顶点着色；,如果用k种颜色可以对G进行正常顶点着色，称G可k正常顶点着色；,对图G正常顶点着色需要的最少颜色数，称为图G的点色数。图G的点色数用 表示。,例1 说明下图的点色数是4。,5 定义1 设G是一个图，对G的每个顶点着色，使得相,6,解：一方面，由图的结构特征容易知道,另一方面，通过具体着色，用4种颜色可以得到该图的一种正常点着色，则：,所以，,6 解：一方面，由图的结构特征容易知道 另一,7,注：对图的正常顶点着色，带来的是图的顶点集合的一种划分方式。所以，对应的实际问题也是分类问题。属于同一种颜色的顶点集合称为一个色组，它们彼此不相邻接，所以又称为点独立集。用点色数种颜色对图G正常着色，称为对图G的最优点着色。,定义2 色数为k的图称为k色图。,(二)、图的点色数的几个结论,定理1 对任意的图G，有：,分析：事实上，定理结论容易想到，因为任意一个顶点度数至多为，因此，正常着色过程中，其邻点最多用去种颜色，所以，至少还有一种色可供该点正常着色使用。,7 注：对图的正常顶点着色，带来的是图的顶点集合的一,8,证明：我们对顶点数作数学归纳证明。,当n=1时，结论显然成立。,设对顶点数少于n的图来说，定理结论成立。考虑一般的n阶图G。,任取v V(G), 令G1=G-v， 由归纳假设：,设是G1的一种(G)+1正常点着色方案，因为v的邻点在下至多用去(G)种色，所以给v染上其邻点没有用过的色，就把扩充成了G的(G)+1着色方案。,对于G来说，可以给出其(G)+1正常点着色算法。,8 证明：我们对顶点数作数学归纳证明。 当n,9,G的(G)+1正常点着色算法,设G=(V, E), V=v1,v2,vn,色集合C=1,2,+1,着色方案为。,(1) 令(v1)=1, i=1;,(2) 若i=n,则停止；否则令：,设k为C-C(vi+1)中的最小整数，令,(3) 令i=i+1,转(2)。,9G的(G)+1正常点着色算法 设G=(V, E),10,例2 给出下图的+1正常点着色。,解：色集C=1, 2, 3, 4, 5,10 例2 给出下图的+1正常点着色。v5v4v3,11,11v5v4v3v2v1v6v5(2)v4(1)v3(3)v,12,注: (1)不能通过上面算法求出色数，例如，根据上面算法，我们求出了一个4色方案，但G是3色图：,(2) WelshPowell稍微对上面算法做了一个修改，着色时按所谓最大度优先策略，即使用上面算法时，按顶点度数由大到小的次序着色。这样的着色方案起到了对上面算法的一个改进作用。,12v5v4v3v2v1v6 注: (1)不能通过上,13,对于简单图G来说，数学家布鲁克斯(Brooks)给出了一个对定理1的色数改进界。这就是下面著名的布鲁克斯定理。,定理2(布鲁克斯，1941) 若G是连通的单图，并且它既不是奇圈，又不是完全图，则：,数学家罗瓦斯在1973年给出了如下证明。,证明：不失一般性，我们可以假设G是正则的，2连通的，最大度3的简单图。原因如下：,(1) 容易证明：若G是非正则连通单图，最大度是，则,事实上，我们可以对G的顶点数作数学归纳证明：,13 对于简单图G来说，数学家布鲁克斯(Brooks,14,当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连通单图，最大度是，则,14 当n=1时，结论显然成立； 设对于阶数,15,(3) (G)3,若不然，结合(2), G为圈。因G不是奇圈，所以定理结论显然成立。,所以，下面只需证明：假设G是正则的，2连通的，最大度3的简单图，且不是完全图或奇圈，有：,分两步完成证明。,1) 在上面条件下，我们证明：G中存在三点x1, x2, xn,使得G -x1, x2连通，x1与x2不邻接，但x1, x2与xn均邻接；,15 (3) (G)3 若不然，结合(2,16,情形1 设G是3连通的正则非完全图。,对于G中点xn, 显然在其邻点中存在两个不邻接顶点x1与x2, 使得G-x1, x2连通。,情形2 设G是连通度为2的正则非完全图。,此时，存在点xn,使得G-xn连通且有割点v, 于是G-xn至少含有两个块。,16 情形1 设G是3连通的正则非完全图。,17,由于G本身2连通，所以G-xn的每个仅含有一个割点的块中均有点与xn邻接。设分属于H1与H2中的点x1与x2，它们与xn邻接。由于x1与x2分属于不同块，所以x1与x2不邻接。又因为3，所以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,xn,17 由于G本身2连通，所以G-xn的每个仅含有一个,18,该顶点序列的特征是，对于1in-1,xi与某个xi+k邻接。,把着色算法用于G，按照上面顶点排序着色，容易知道，用(G)种颜色可以完成G的正常点着色。,对于简单图的点色数，还可以在定理2的基础上获得改进。,定义3 设G是至少有一条边的简单图，定义：,其中N(u)为G中点u的邻域。称2(G)为G的次大度。,18 该顶点序列的特征是，对于1in-1,xi与,19,如果令：,那么，,例如：求下面图的次大度2(G),G1,G2,19 如果令： 那么， 例如：求下面,20,解：(1),(2),20 解：(1) G1v5v4v3v2v1G2v5v,21,注：由次大度的定义知：2(G)(G),定理3 设G是非空简单图，则：,注：定理3是对定理2的一个改进！,21G2v5v4v3v2v1v8v7v6v9 注：由,22,例如：对下面单图来说，由定理2得：,而由定理3得：,推论：设G是非空简单图，若G中最大度点互不邻接，则有：,22G2v5v4v3v2v1v8v7v6v9 例如：,23,1、四色定理,(三)、四色与五色定理,1852年，刚毕业于伦敦大学的格斯里(18311899)发现：给一张平面地图正常着色，至少需要4种颜色。这就是著名的4色定理。,格斯里把他的证明通过他弟弟转交给著名数学家摩尔根，引起摩尔根极大兴趣并于当天给数学家哈密尔顿写了封相关信件。但没有引起哈密尔顿的注意。,直到1878年，在英国数学会议上，数学家凯莱才再一次提到4色问题。,23 1、四色定理(三)、四色与五色定理 1,24,1879年7月，业余数学家肯普(1849-1922）在英国自然杂志上宣称证明了4色定理。肯普是凯莱在剑桥大学的学生。,1890年，英国数学家希五德发表文章地图染色定理，通过构造反例，指出了肯普证明中的缺陷。后来，西五德一直研究4色问题60年。,泰特在此期间也研究4色问题，但其证明被托特否定。,希五德文章之后，4色问题研究进程开始走向停滞。,到了20世纪，美国数学家比尔荷夫提出可约性概念，在此基础上，德国数学家Heesch(19061995)认为，可以通过寻找所谓的不可约构形来证明4色定理。,24 1879年7月，业余数学家肯普(1849-,25,Heesch估计不可约构形集合可能包含10000个元素，手工验证是不太可能。于是他给出了一种可用计算机来验证的方法。,20世纪70年代，Haken和他的学生Appel着力用计算机方法证明4色定理，借助于Appel在编程方面的深厚功底。他们于1976年6月终于成功解决了寻找不可约构形集合中的元素，宣告4色定理的成功证明。数学家托特在图论顶级刊物图论杂志上写了一首诗：,Wolfgang Haken,重重打击着巨妖,一次！两次！三次！四次！,他说：“妖怪已经不存在了.”,25 Heesch估计不可约构形集合可能包含100,26,2、五色定理,定理4 (希五德) 每个平面图是5可着色的。,根据平面图和其对偶图的关系，上面定理等价于每个平面图是5可顶点正常着色的。,证明：我们对图的顶点作数学归纳证明。,当n=1时，结论显然。,设n=k时，结论成立。考虑n=k+1的平面图G。,因G是平面图，所以(G)5,设d(u)=(G)5。,26 2、五色定理 定理4 (希五德) 每个,27,令G1=G u。由归纳假设，G1是5可顶点正常着色的。设是G1的5着色方案。,(1) 如果d(u)=(G)5, 显然可以扩充为G的5正常顶点着色；,(2) 如果d(u)=(G) = 5, 分两种情况讨论。,情形1 在下，如果u的邻接点中，至少有两个顶点着相同颜色，则容易知道，可以扩充为G的5正常顶点着色；,情形2 在下，设u的邻接点中，5个顶点着了5种不同颜色。,27 令G1=G u。由归纳假设，G1是5可顶点,28,不失一般性，设(xi)=i (1i5)。,设H (i, j)表示着i和j色的点在G1中的点导出子图。,如果x1与x3属于H(1, 3) 的不同分支。则通过交换含x1的分支中的着色顺序，可得到G1的新正常点着色方案，使x1与x3着同色，于是由情形1，可以得到G的5正常顶点着色方案；,28 不失一般性，设(xi)=i (1i5)。,29,设x1与x3属于H(1, 3) 的相同分支。,在上面假设下，x2与x4必属于H(2, 4) 的不同分支。否则，将会得到H(1, 3) 与H(2, 4) 的交叉点。因此，可以扩充为G的5正常顶点着色。,29 设x1与x3属于H(1, 3) 的相同分支。x,30,(四)、顶点着色的应用,图的正常顶点着色对应的实际问题是“划分”问题。,例1 课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论(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;,30(四)、顶点着色的应用 图的正常顶点着色对应的实,31,A10: GT, S。,解：把课程模型为图G的顶点，两顶点连线当且仅当有某个学生同时选了这两门课程。,31 A10: GT, S。 解：把课程模型,32,如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状态图中求对应于点色数的着色。,(1) 求点色数,一方面，因图中含有奇圈(红色边), 所以，点色数至少为3。又因为点LA与该圈上每一个点均邻接，所以，点色数至少为4.,另一方面，我们用4种色实现了G的正常点着色，所以，图的点色数为4.,32 如果我们用同一颜色给同一时段的课程顶点染色，那,33,(2) 求安排-具体着色,33 (2) 求安排-具体着色GTMAGACL,34,例2 交通灯的相位设置问题：如图所示，列出了繁华街道路口处的交通车道L1,L2,L9。在此路口处安置了交通灯。当交通灯处于某个相位时，亮绿灯的车道上的车辆就可以安全通过路口。为了(最终)让所有的车辆的灯都能够安全通过路口，对于交通灯来说，所需要的相位的最小数是多少？,34 例2 交通灯的相位设置问题：如图所示，列出了繁,35,解：车道模型为顶点，两点连线当且仅当两个车道上的车不能同时安全地进入路口。,问题转化为求G的点色数。一方面，G中含有K4,所以，点色数至少为4；,35 解：车道模型为顶点，两点连线当且仅当两个车道上,36,另一方面，通过尝试，用4种色实现了正常点着色。,所以，最小相位为4。,P187-190 习题7 ：7-9,36 另一方面，通过尝试，用4种色实现了正常点着色。,