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