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

1、1本次课主要内容本次课主要内容(一一)、相关概念、相关概念(二二)、图的点色数的几个结论、图的点色数的几个结论(三三)、四色与五色定理、四色与五色定理图的顶点着色图的顶点着色(四四)、顶点着色的应用、顶点着色的应用2 跟图的边着色问题一样，生活中的很多问题，也可跟图的边着色问题一样，生活中的很多问题，也可以模型为所谓的图的顶点着色问题来处理。例如课程安以模型为所谓的图的顶点着色问题来处理。例如课程安排问题。排问题。(一一)、相关概念、相关概念 课程安排问题：某大学数学系要为这个夏季安排课课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论程表。所要开设的课程为：图论(GT)

2、,(GT),统计学统计学(S),(S),线性线性代数代数(LA),(LA),高等微积分高等微积分(AC),(AC),几何学几何学(G),(G),和近世代数和近世代数(MA)(MA)。现有。现有1010名学生名学生(如下所示如下所示)需要选修这些课程。根需要选修这些课程。根据这些信息，确定开设这些课程所需要的最少时间段数，据这些信息，确定开设这些课程所需要的最少时间段数，使得学生选课不会发生冲突。使得学生选课不会发生冲突。(学生用学生用A Ai i表示）表示）A A1 1:LA,S;A:LA,S;A2 2:MA,LA,G;A:MA,LA,G;A3 3:MA,G,:MA,G,LA;LA;A A4

3、4:G,LA,AC;A:G,LA,AC;A5 5:AC,LA,S;A:AC,LA,S;A6 6:G,:G,AC;AC;A A7 7:GT,MA,LA;A:GT,MA,LA;A8 8:LA,GT,S;A:LA,GT,S;A9 9:AC,:AC,S,LA;S,LA;3 A A1010:GT,S:GT,S。把课程模型为图把课程模型为图G G的顶点，两顶点连线当且仅当有的顶点，两顶点连线当且仅当有某个学生同时选了这两门课程。某个学生同时选了这两门课程。GTMAGACLAS选课状态图选课状态图4 如果我们用同一颜色给同一时段的课程顶点染色，如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状

4、态图中求所谓的点色数问题。那么，问题转化为在状态图中求所谓的点色数问题。GTMAGACLAS选课状态图选课状态图5 定义定义1 1 设设G G是一个图，对是一个图，对G G的每个顶点着色，使得相的每个顶点着色，使得相邻顶点着不同颜色，称为对邻顶点着不同颜色，称为对G G的正常顶点着色；的正常顶点着色；如果用如果用k k种颜色可以对种颜色可以对G G进行正常顶点着色，称进行正常顶点着色，称G G可可k k正常顶点着色；正常顶点着色；对图对图G G正常顶点着色需要的最少颜色数，称为图正常顶点着色需要的最少颜色数，称为图G G的的点色数。图点色数。图G G的点色数用的点色数用 表示。表示。()G 例

5、例1 1 说明下图的点色数是说明下图的点色数是4 4。GTMAGACLAS6 解：一方面，由图的结构特征容易知道解：一方面，由图的结构特征容易知道()4G 另一方面，通过具体着色，用另一方面，通过具体着色，用4 4种颜色可以得到该种颜色可以得到该图的一种正常点着色，则：图的一种正常点着色，则：()4GGTMAGACLAS 所以，所以，()4G7 注：对图的正常顶点着色，带来的是图的顶点集合注：对图的正常顶点着色，带来的是图的顶点集合的一种划分方式。所以，对应的实际问题也是分类问题。的一种划分方式。所以，对应的实际问题也是分类问题。属于同一种颜色的顶点集合称为一个色组，它们彼此不属于同一种颜色的

6、顶点集合称为一个色组，它们彼此不相邻接，所以又称为点独立集。用点色数种颜色对图相邻接，所以又称为点独立集。用点色数种颜色对图G G正正常着色，称为对图常着色，称为对图G G的最优点着色。的最优点着色。定义定义2 2 色数为色数为k k的图称为的图称为k k色图。色图。(二二)、图的点色数的几个结论、图的点色数的几个结论 定理定理1 1 对任意的图对任意的图G G，有：，有：()()1GG 分析：事实上，定理结论容易想到，因为任意一个顶分析：事实上，定理结论容易想到，因为任意一个顶点度数至多为点度数至多为，因此，正常着色过程中，其邻点最多用去，因此，正常着色过程中，其邻点最多用去种颜色，所以，至

7、少还有一种色可供该点正常着色使用。种颜色，所以，至少还有一种色可供该点正常着色使用。8 证明：我们对顶点数作数学归纳证明。证明：我们对顶点数作数学归纳证明。当当n=1n=1时，结论显然成立。时，结论显然成立。设对顶点数少于设对顶点数少于n n的图来说，定理结论成立。考虑一的图来说，定理结论成立。考虑一般的般的n n阶图阶图G G。任取任取v V(G),v V(G),令令G G1 1=G-v=G-v，由归纳假设：由归纳假设：11()()1()1GGG 设设是是G G1 1的一种的一种(G)+1(G)+1正常点着色方案，因为正常点着色方案，因为v v的的邻点在邻点在下至多用去下至多用去(G)(G)

8、种色，所以给种色，所以给v v染上其邻点没有染上其邻点没有用过的色，就把用过的色，就把扩充成了扩充成了G G的的(G)+1(G)+1着色方案。着色方案。对于对于G G来说，可以给出其来说，可以给出其(G)+1(G)+1正常点着色算法。正常点着色算法。9G G的的(G)+1(G)+1正常点着色算法正常点着色算法 设设G=(V,E),V=G=(V,E),V=v v1 1,v,v2 2,v,vn n,色集合色集合C=C=1,2,1,2,+1+1,着色方案为着色方案为。(1)(1)令令(v(v1 1)=1,i=1;)=1,i=1;(2)(2)若若i=n,i=n,则停止；否则令：则停止；否则令：11()

9、(),iijiC vvjivv并且与相邻 设设k k为为C-C(vC-C(vi+1i+1)中的最小整数，令中的最小整数，令+1()=ivk (3)(3)令令i=i+1,i=i+1,转转(2)(2)。10 例例2 2 给出下图的给出下图的+1+1正常点着色。正常点着色。v5v4v3v2v1v6 解：色集解：色集C=C=1,2,3,4,51,2,3,4,51(1),()=1v 22(2),()=1,()2,3,4,5,2C vCC vk2(1),()=2v33(2),()=1,2,()3,4,5,3C vCC vk11v5v4v3v2v1v63(1),()=3v 44(2),()=3,()1,2,

10、4,5,1C vCC vk4(1),()=1v 55(2),()=1,()2,3,4,5,2C vCC vk5(1),()=2v65(2),()=1,2,3,()4,5,4C vCC vk6(1),()=4vv5(2)v4(1)v3(3)v2(2)v1(1)v6(4)12v5v4v3v2v1v6 注注:(1):(1)不能通过上面算法求出色数，例如，根据上面不能通过上面算法求出色数，例如，根据上面算法，我们求出了一个算法，我们求出了一个4 4色方案，但色方案，但G G是是3 3色图：色图：(2)(2)WelshPowellWelshPowell稍微对上面算法做了一个修改，着稍微对上面算法做了一个

11、修改，着色时按所谓最大度优先策略，即使用上面算法时，按顶点度色时按所谓最大度优先策略，即使用上面算法时，按顶点度数由大到小的次序着色。这样的着色方案起到了对上面算法数由大到小的次序着色。这样的着色方案起到了对上面算法的一个改进作用。的一个改进作用。13 对于简单图对于简单图G G来说，数学家布鲁克斯来说，数学家布鲁克斯(Brooks)(Brooks)给出给出了一个对定理了一个对定理1 1的色数改进界。这就是下面著名的布鲁的色数改进界。这就是下面著名的布鲁克斯定理。克斯定理。定理定理2(2(布鲁克斯，布鲁克斯，1941)1941)若若G G是连通的单图，并且是连通的单图，并且它既不是奇圈，又不是

12、完全图，则：它既不是奇圈，又不是完全图，则：()()GG 数学家罗瓦斯在数学家罗瓦斯在19731973年给出了如下证明。年给出了如下证明。证明：不失一般性，我们可以假设证明：不失一般性，我们可以假设G G是正则的，是正则的，2 2连通的，最大度连通的，最大度3 3的简单图。原因如下：的简单图。原因如下：(1)(1)容易证明：若容易证明：若G G是非正则连通单图，最大度是是非正则连通单图，最大度是，则则()()GG 事实上，我们可以对事实上，我们可以对G G的顶点数作数学归纳证明：的顶点数作数学归纳证明：14 当当n=1n=1时，结论显然成立；时，结论显然成立；设对于阶数小于设对于阶数小于n n

13、的简单非正则连通单图来说，结的简单非正则连通单图来说，结论成立。假设论成立。假设G G是阶数为是阶数为n n的非正则连通单图。的非正则连通单图。设设u u是是G G中顶点，且中顶点，且d(u)=d(u)=，考虑，考虑G G1 1=G-u=G-u 若若G G1 1是正则单图，则是正则单图，则(G(G1 1)=)=(G)-1(G)-1。于是。于是G G1 1是可是可(G)(G)顶点正常着色的，从而，顶点正常着色的，从而，G G是可是可(G)(G)正常顶点着色正常顶点着色的；的；若若G G1 1是非正则单图，则由数学归纳，是非正则单图，则由数学归纳，G G1 1是可是可(G)(G)顶顶点正常着色的，

14、从而，点正常着色的，从而，G G是可是可(G)(G)正常顶点着色的。正常顶点着色的。(2)(2)容易证明：若容易证明：若G G是是1 1连通单图，最大度是连通单图，最大度是，则，则()()GG 15 (3)(3)(G)3(G)3 若不然，结合若不然，结合(2),G(2),G为圈。因为圈。因G G不是奇圈，所以定理不是奇圈，所以定理结论显然成立。结论显然成立。所以，下面只需证明：假设所以，下面只需证明：假设G G是正则的，是正则的，2 2连通的，连通的，最大度最大度3 3的简单图，且不是完全图或奇圈，有：的简单图，且不是完全图或奇圈，有：()()GG 分两步完成证明。分两步完成证明。1)1)在上

15、面条件下，我们证明：在上面条件下，我们证明：G G中存在三点中存在三点x x1 1,x,x2 2,x xn n,使得使得G-G-x x1 1,x,x2 2连通，连通，x x1 1与与x x2 2不邻接，但不邻接，但x x1 1,x,x2 2与与x xn n均均邻接；邻接；16 情形情形1 1 设设G G是是3 3连通的正则非完全图。连通的正则非完全图。对于对于G G中点中点x xn n,显然在其邻点中存在两个不邻接顶点显然在其邻点中存在两个不邻接顶点x x1 1与与x x2 2,使得使得G-G-x x1 1,x,x2 2连通。连通。情形情形2 2 设设G G是连通度为是连通度为2 2的正则非完

16、全图。的正则非完全图。此时，存在点此时，存在点x xn n,使得使得G-xG-xn n连通且有割点连通且有割点v,v,于是于是G-xG-xn n至少含有两个块。至少含有两个块。vG-v块块块块块块17 由于由于G G本身本身2 2连通，所以连通，所以G-xG-xn n的每个仅含有一个割点的的每个仅含有一个割点的块中均有点与块中均有点与x xn n邻接。设分属于邻接。设分属于H H1 1与与H H2 2中的点中的点x x1 1与与x x2 2，它们，它们与与x xn n邻接。由于邻接。由于x x1 1与与x x2 2分属于不同块，所以分属于不同块，所以x x1 1与与x x2 2不邻接。不邻接。

17、又因为又因为33，所以，所以G-G-x x1 1,x,x2 2连通。连通。2)2)对对G G中顶点进行如下排序：中顶点进行如下排序：令令x xn-1n-1 V(G)-V(G)-x x1 1,x,x2 2,x,xn n且与且与x xn n邻接；邻接；x xn-2n-2 V(G)-V(G)-x x1 1,x,x2 2,x,xn n，x xn-1n-1且与且与x xn n或或x xn-1n-1邻接；邻接；x xn-3n-3 V(G)-V(G)-x x1 1,x,x2 2,x,xn n，x xn-1n-1,x,xn-2n-2且与且与x xn n或或x xn-1n-1或或x xn-2n-2邻接；邻接；不

18、断这样作下去，可得到不断这样作下去，可得到G G的顶点排序：的顶点排序：x x1 1,x,x2 2,x,xn n18 该顶点序列的特征是，对于该顶点序列的特征是，对于1in-1,x1in-1,xi i与某个与某个x xi+i+k k邻邻接。接。把着色算法用于把着色算法用于G G，按照上面顶点排序着色，容易知，按照上面顶点排序着色，容易知道，用道，用(G)(G)种颜色可以完成种颜色可以完成G G的正常点着色。的正常点着色。对于简单图的点色数，还可以在定理对于简单图的点色数，还可以在定理2 2的基础上获得的基础上获得改进。改进。定义定义3 3 设设G G是至少有一条边的简单图，定义：是至少有一条边

19、的简单图，定义：2()()()()()maxmax()uVGvNudvd uGd v 其中其中N(u)N(u)为为G G中点中点u u的邻域。称的邻域。称2 2(G)(G)为为G G的次大度。的次大度。19 如果令：如果令：2()(),()()()VGv vV GN vud ud v中存在点，满足 那么，那么，22()max()()Gd v vVG 例如：求下面图的次大度例如：求下面图的次大度2 2(G)(G)G1G220 解：解：(1)(1)G1v5v4v3v2v1G2v5v4v3v2v1v8v7v6v9211()(),()()()VGv vV GN vud ud v中存在点，满足1234,

20、v vvv22()max()()1Gd v vVG (2)(2)222()(),()()()VGv vV GN vud ud v中存在点，满足21G2v5v4v3v2v1v8v7v6v91235,869,v vvv vvv22()max()()3Gd v vVG 注：由次大度的定义知：注：由次大度的定义知：2 2(G)(G)(G)(G)定理定理3 3 设设G G是非空简单图，则：是非空简单图，则：2()()1GG 注：定理注：定理3 3是对定理是对定理2 2的一个改进！的一个改进！22G2v5v4v3v2v1v8v7v6v9 例如：对下面单图来说，由定理例如：对下面单图来说，由定理2 2得：得

21、：22()()5GG 而由定理而由定理3 3得：得：222()()4GG 推论：设推论：设G G是非空简单图，若是非空简单图，若G G中最大度点互不邻接，中最大度点互不邻接，则有：则有：()()GG 23 1 1、四色定理、四色定理(三三)、四色与五色定理、四色与五色定理 1852 1852年，刚毕业于伦敦大学的格斯里年，刚毕业于伦敦大学的格斯里(18311899)(18311899)发发现：给一张平面地图正常着色，至少需要现：给一张平面地图正常着色，至少需要4 4种颜色。这就是种颜色。这就是著名的著名的4 4色定理。色定理。格斯里把他的证明通过他弟弟转交给著名数学家摩尔格斯里把他的证明通过他

22、弟弟转交给著名数学家摩尔根，引起摩尔根极大兴趣并于当天给数学家哈密尔顿写了根，引起摩尔根极大兴趣并于当天给数学家哈密尔顿写了封相关信件。但没有引起哈密尔顿的注意。封相关信件。但没有引起哈密尔顿的注意。直到直到18781878年，在英国数学会议上，数学家凯莱才再一年，在英国数学会议上，数学家凯莱才再一次提到次提到4 4色问题。色问题。24 1879 1879年年7 7月，业余数学家肯普月，业余数学家肯普(1849-1922(1849-1922）在英国）在英国自然杂志上宣称证明了自然杂志上宣称证明了4 4色定理。肯普是凯莱在剑桥大学的色定理。肯普是凯莱在剑桥大学的学生。学生。18901890年，英

23、国数学家希五德发表文章地图染色定理，年，英国数学家希五德发表文章地图染色定理，通过构造反例，指出了肯普证明中的缺陷。后来，西五德通过构造反例，指出了肯普证明中的缺陷。后来，西五德一直研究一直研究4 4色问题色问题6060年。年。泰特在此期间也研究泰特在此期间也研究4 4色问题，但其证明被托特否定。色问题，但其证明被托特否定。希五德文章之后，希五德文章之后，4 4色问题研究进程开始走向停滞。色问题研究进程开始走向停滞。到了到了2020世纪，美国数学家比尔荷夫提出可约性概念，世纪，美国数学家比尔荷夫提出可约性概念，在此基础上，德国数学家在此基础上，德国数学家Heesch(19061995)Hees

24、ch(19061995)认为，可以认为，可以通过寻找所谓的不可约构形来证明通过寻找所谓的不可约构形来证明4 4色定理。色定理。25 Heesch Heesch估计不可约构形集合可能包含估计不可约构形集合可能包含1000010000个元素，个元素，手工验证是不太可能。于是他给出了一种可用计算机来验手工验证是不太可能。于是他给出了一种可用计算机来验证的方法。证的方法。20 20世纪世纪7070年代，年代，HakenHaken和他的学生和他的学生AppelAppel着力用计算着力用计算机方法证明机方法证明4 4色定理，借助于色定理，借助于AppelAppel在编程方面的深厚功底。在编程方面的深厚功底

25、。他们于他们于19761976年年6 6月终于成功解决了寻找不可约构形集合中的月终于成功解决了寻找不可约构形集合中的元素，宣告元素，宣告4 4色定理的成功证明。数学家托特在图论顶级刊色定理的成功证明。数学家托特在图论顶级刊物物图论杂志图论杂志上写了一首诗：上写了一首诗：Wolfgang Haken Wolfgang Haken 重重打击着巨妖重重打击着巨妖 一次！两次！三次！四次！一次！两次！三次！四次！他说：他说：“妖怪已经不存在了妖怪已经不存在了.”.”26 2 2、五色定理、五色定理 定理定理4(4(希五德希五德)每个平面图是每个平面图是5 5可着色的。可着色的。根据平面图和其对偶图的关

26、系，上面定理等价于根据平面图和其对偶图的关系，上面定理等价于每个平面图是每个平面图是5 5可顶点正常着色的。可顶点正常着色的。证明：我们对图的顶点作数学归纳证明。证明：我们对图的顶点作数学归纳证明。当当n=1n=1时，结论显然。时，结论显然。设设n=kn=k时，结论成立。考虑时，结论成立。考虑n=k+1n=k+1的平面图的平面图G G。因因G G是平面图，所以是平面图，所以(G)5(G)5 设设d(u)=d(u)=(G)5(G)5。27 令令G G1 1=G u=G u。由归纳假设，。由归纳假设，G G1 1是是5 5可顶点正常着色可顶点正常着色的。设的。设是是G G1 1的的5 5着色方案。

27、着色方案。(1)(1)如果如果d(u)=d(u)=(G)5,(G)5,显然显然可以扩充为可以扩充为G G的的5 5正常顶点着色；正常顶点着色；(2)(2)如果如果d(u)=d(u)=(G)=5,(G)=5,分两种情况讨论。分两种情况讨论。情形情形1 1 在在下，如果下，如果u u的邻接点中，至少有两个顶的邻接点中，至少有两个顶点着相同颜色，则容易知道，点着相同颜色，则容易知道，可以扩充为可以扩充为G G的的5 5正常顶正常顶点着色；点着色；情形情形2 2 在在下，设下，设u u的邻接点中，的邻接点中，5 5个顶点着了个顶点着了5 5种种不同颜色。不同颜色。28 不失一般性，设不失一般性，设(x

28、(xi i)=i(1i5)=i(1i5)。x5x4x3x2x1u 设设H(i,j)H(i,j)表示着表示着i i和和j j色的点在色的点在G G1 1中的点导出子中的点导出子图。图。如果如果x x1 1与与x x3 3属于属于H(1,3)H(1,3)的不同分支。则通过交换的不同分支。则通过交换含含x x1 1的分支中的着色顺序，可得到的分支中的着色顺序，可得到G G1 1的新正常点着色方的新正常点着色方案，使案，使x x1 1与与x x3 3着同色，于是由情形着同色，于是由情形1 1，可以得到，可以得到G G的的5 5正常正常顶点着色方案；顶点着色方案；29 设设x x1 1与与x x3 3属

29、于属于H(1,3)H(1,3)的相同分支。的相同分支。x5x4x3x2x1u3131 在上面假设下，在上面假设下，x x2 2与与x x4 4必属于必属于H(2,4)H(2,4)的不同分支。的不同分支。否则，将会得到否则，将会得到H(1,3)H(1,3)与与H(2,4)H(2,4)的交叉点。因此，的交叉点。因此，可以扩充为可以扩充为G G的的5 5正常顶点着色。正常顶点着色。30(四四)、顶点着色的应用、顶点着色的应用 图的正常顶点着色对应的实际问题是图的正常顶点着色对应的实际问题是“划分划分”问问题。题。例例1 1 课程安排问题：某大学数学系要为这个夏季安课程安排问题：某大学数学系要为这个夏

30、季安排课程表。所要开设的课程为：图论排课程表。所要开设的课程为：图论(GT),(GT),统计学统计学(S),(S),线性代数线性代数(LA),(LA),高等微积分高等微积分(AC),(AC),几何学几何学(G),(G),和近世代和近世代数数(MA)(MA)。现有。现有1010名学生名学生(如下所示如下所示)需要选修这些课程。需要选修这些课程。根据这些信息，确定开设这些课程所需要的最少时间段根据这些信息，确定开设这些课程所需要的最少时间段数，使得学生选课不会发生冲突。数，使得学生选课不会发生冲突。(学生用学生用A Ai i表示）表示）A A1 1:LA,S;A:LA,S;A2 2:MA,LA,G

31、;A:MA,LA,G;A3 3:MA,G,:MA,G,LA;LA;A A4 4:G,LA,AC;A:G,LA,AC;A5 5:AC,LA,S;A:AC,LA,S;A6 6:G,:G,AC;AC;A A7 7:GT,MA,LA;A:GT,MA,LA;A8 8:LA,GT,S;A:LA,GT,S;A9 9:AC,:AC,S,LA;S,LA;31 A A1010:GT,S:GT,S。解：把课程模型为图解：把课程模型为图G G的顶点，两顶点连线当且仅的顶点，两顶点连线当且仅当有某个学生同时选了这两门课程。当有某个学生同时选了这两门课程。GTMAGACLAS选课状态图选课状态图32 如果我们用同一颜色给

32、同一时段的课程顶点染色，如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状态图中求对应于点色数的着色。那么，问题转化为在状态图中求对应于点色数的着色。(1)(1)求点色数求点色数 一方面，因图中含有奇圈一方面，因图中含有奇圈(红色边红色边),),所以，点色数至少为所以，点色数至少为3 3。又因为点。又因为点LALA与该圈上每一个与该圈上每一个点均邻接，所以，点色数至少为点均邻接，所以，点色数至少为4.4.GTMAGACLAS选课状态图选课状态图 另一方面，我们用另一方面，我们用4 4种色实现了种色实现了G G的正常点着色，所的正常点着色，所以，图的点色数为以，图的点色数为4.4.

33、33 (2)(2)求安排求安排-具体着色具体着色GTMAGACLAS选课状态图选课状态图34 例例2 2 交通灯的相位设置问题：如图所示，列出了繁华交通灯的相位设置问题：如图所示，列出了繁华街道路口处的交通车道街道路口处的交通车道L1,L2,L9L1,L2,L9。在此路口处安置了交。在此路口处安置了交通灯。当交通灯处于某个相位时，亮绿灯的车道上的车辆就通灯。当交通灯处于某个相位时，亮绿灯的车道上的车辆就可以安全通过路口。为了可以安全通过路口。为了(最终最终)让所有的车辆的灯都能够安让所有的车辆的灯都能够安全通过路口，对于交通灯来说，所需要的相位的最小数是多全通过路口，对于交通灯来说，所需要的相

34、位的最小数是多少？少？L5L4L3L2L1L9L8L7L635 解：车道模型为顶点，两点连线当且仅当两个车道上解：车道模型为顶点，两点连线当且仅当两个车道上的车不能同时安全地进入路口。的车不能同时安全地进入路口。L9L8L7L6L5L4L3L2L1G 问题转化为求问题转化为求G G的点色数。一方面，的点色数。一方面，G G中含有中含有K K4 4,所以，所以，点色数至少为点色数至少为4 4；L9L8L7L6L5L4L3L2L1G36 另一方面，通过尝试，用另一方面，通过尝试，用4 4种色实现了正常点着色。种色实现了正常点着色。所以，最小相位为所以，最小相位为4 4。L9L8L7L6L5L4L3L2L1G211224343P187-190 P187-190 习题习题7 7：7-97-9