图论课件--图的顶点着色

《图论课件--图的顶点着色》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论及其应用应用数学学院1本次课主要内容(一)、相关概念(二)、图的点色数的几个结论(三)、四色与五色定理图的顶点着色(四)、顶点着色的应用2跟图的边着色问题一样，生活中的很多问题，也可以模型为所谓的图的顶点着色问题来处理。例如课程安排问题。(一)、相关概念课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论(GT),统计学(S),线性代数(LA),高等微积分(AC),几何学(G),和近世代数(MA)。现有10名学生(如下所示)需要选修这些课程。根据这些信息，确定开设这些课程所需要的最少时间段数，使得

2、学生选课不会发生冲突。(学生用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;3A10:GT,S。把课程模型为图G的顶点，两顶点连线当且仅当有某个学生同时选了这两门课程。GTMAGACLAS选课状态图4如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状态图中求所谓的点色数问题。GTMAGACLAS选课状态图5定义1设G是一个图，对G的每个顶点着色，使得相邻顶点

3、着不同颜色，称为对G的正常顶点着色；如果用k种颜色可以对G进行正常顶点着色，称G可k正常顶点着色；对图G正常顶点着色需要的最少颜色数，称为图G的点色数。图G的点色数用表示。例1说明下图的点色数是4。GTMAGACLAS6解：一方面，由图的结构特征容易知道另一方面，通过具体着色，用4种颜色可以得到该图的一种正常点着色，则：GTMAGACLAS所以，7注：对图的正常顶点着色，带来的是图的顶点集合的一种划分方式。所以，对应的实际问题也是分类问题。属于同一种颜色的顶点集合称为一个色组，它们彼此不相邻接，所以又称为点独立集。用点色

4、数种颜色对图G正常着色，称为对图G的最优点着色。定义2色数为k的图称为k色图。(二)、图的点色数的几个结论定理1对任意的图G，有：分析：事实上，定理结论容易想到，因为任意一个顶点度数至多为Δ，因此，正常着色过程中，其邻点最多用去Δ种颜色，所以，至少还有一种色可供该点正常着色使用。8证明：我们对顶点数作数学归纳证明。当n=1时，结论显然成立。设对顶点数少于n的图来说，定理结论成立。考虑一般的n阶图G。任取v∈V(G),令G1=G-v，由归纳假设：设п是G1的一种Δ(G)+1正常点着色方案，因为v的邻点在п下至多用去Δ(G)

5、种色，所以给v染上其邻点没有用过的色，就把п扩充成了G的Δ(G)+1着色方案。对于G来说，可以给出其Δ(G)+1正常点着色算法。9G的Δ(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)。10例2给出下图的Δ+1正常点着色。v5v4v3v2v1v6解：色集C=｛1,2,3,4,5｝11v5v4v3v2v1v6v5(2)v4

6、(1)v3(3)v2(2)v1(1)v6(4)12v5v4v3v2v1v6注:(1)不能通过上面算法求出色数，例如，根据上面算法，我们求出了一个4色方案，但G是3色图：(2)Welsh—Powell稍微对上面算法做了一个修改，着色时按所谓最大度优先策略，即使用上面算法时，按顶点度数由大到小的次序着色。这样的着色方案起到了对上面算法的一个改进作用。13对于简单图G来说，数学家布鲁克斯(Brooks)给出了一个对定理1的色数改进界。这就是下面著名的布鲁克斯定理。定理2(布鲁克斯，1941)若G是连通的单图，并且它既不是奇圈，

7、又不是完全图，则：数学家罗瓦斯在1973年给出了如下证明。证明：不失一般性，我们可以假设G是正则的，2连通的，最大度Δ≥3的简单图。原因如下：(1)容易证明：若G是非正则连通单图，最大度是Δ，则事实上，我们可以对G的顶点数作数学归纳证明：14当n=1时，结论显然成立；设对于阶数小于n的简单非正则连通单图来说，结论成立。假设G是阶数为n的非正则连通单图。设u是G中顶点，且d(u)=δ<Δ，考虑G1=G-u若G1是正则单图，则Δ(G1)=Δ(G)-1。于是G1是可Δ(G)顶点正常着色的，从而，G是可Δ(G)正常顶点着色的；若

8、G1是非正则单图，则由数学归纳，G1是可Δ(G)顶点正常着色的，从而，G是可Δ(G)正常顶点着色的。(2)容易证明：若G是1连通单图，最大度是Δ，则15(3)Δ(G)≥3若不然，结合(2),G为圈。因G不是奇圈，所以定理结论显然成立。所以，下面只需证明：假设G是正则的，2连通的，最大度Δ≥3的简单图，且不是完全图或奇