⚠ 转载请注明出处:作者:ZobinHuang,更新日期:May.9 2022
本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可,在进行使用或分享前请查看权限要求。若发现侵权行为,会采取法律手段维护作者正当合法权益,谢谢配合。
目录
有特定需要的内容直接跳转到相关章节查看即可。
1. 点着色的概念
1.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 |
A10 | GT, S |
假如我们把课程转化为图 G 的顶点,两顶点连线当且仅当有某个学生同时选了这两门课程,如下图所示:

如果我们用同一颜色给冲突的课程所代表顶点染不同色, 那么问题转化为在图中求所谓
1.2 相关概念定义
设 G 是一个图,对 G 的每个顶点着色,使得相邻顶点着不同颜色,称为对 G 的
如果用 k 种颜色可以对 G 进行正常点着色,称 G
对图 G 正常顶点着色需要的最少颜色数,称为图 G 的
2. 图的点色数的几个结论
显然 χ(G)≤n,且仅对 Kn 有 χ(Kn)=cl(Kn)=n,其中 cl(Kn) 指的是 Kn 的最大团的阶数。
下面我们给出图的点色数的几个结论。
证明:
事实上,由定理结论容易想到,因为任意一个顶点度数至多为 Δ。因此,正常着色过程中,其邻点最多用去 Δ 种颜色。所以,至少还有一种色可供该点正常着色使用。
下面我们给出严格证明。我们对顶点数作数学归纳证明:
当 n=1 时,结论显然成立。
设对顶点数少于 n 的图来说,定理结论成立。考虑一般的 n 阶图 G。
任取 v∈V(G),令 G1=G−v,由归纳假设可得:
设 π 是 G1 的一种 Δ(G)+1 正常点着色方案,因为 v 的邻点在 π 下至多用去 Δ(G) 种色,所以给 v 染上其邻点没有用过的色,就把 π 扩充成了 G 的 Δ(G)+1 的着色方案。
对于 G 来说,可以给出其 Δ(G)+1 正常点着色算法。
下面我们给出图 G 的 Δ(G)+1 的正常点着色算法。设 G=(V,E),V={v1,v2,…,vn},色集合C={1,2,…,Δ+1},着色方案为 π。
- 令 π(v1)=1,i=1;
- 若 i=n,则停止; 否则若 k 为与 vi+1 相邻的顶点里未使用的标号最小的色号,则令 π(vi+1)=k;
- 令 i=i+1,转 (2)
值得注意的是,虽然上述算法能够完成对图 G 的正常点着色,但是不能够求出来图 G 的点色数。
下面给出
3. 四色定理与五色定理
3.1 四色定理

四色定理曾经是著名的数学猜想,在上个世纪七十年代被使用计算机方法予以了证明。详细的四色定理的发展历史可参考 4_color_wiki。
3.2 五色定理
下面给出五色定理。
证明:
我们对图的顶点数进行归纳。当 n=1 时,结论显然。
假设当 n=k 时结论成立,考虑当 n=k+1 时的连通平面图 G。
因为图 G 是连通平面图,所以 δ(G)≤5。设最小度点 d(u)=δ(G)≤5,令 G1=G-u,由归纳假设可得,G1 是 5-可顶点正常着色的。设 π 是 G1 的 5 着色方案。
(1) 如果 d(u)=δ(G)<5,显然 π 可以扩充为 G 的 5 正常顶点着色,u 只要使用其不超过 4 个的邻居没有使用的颜色即可。
(2) 如果 d(u)=δ(G)=5,则需要分两种情况进行讨论。
-
在 π 下,如果 u 的邻接点中,至少有两个顶点着相同颜色,则容易知道,π 可以扩充为 G 的 5-正常顶点着色;
-
在 π 下,设 u 的邻接点中,5 个顶点着了 5 种不同颜色:
Figure 3: 第二种情况 不失一般性,设 π(xi)=i(1≤i≤5)。设 H(i,j) 表示着 i 和 j 色的点在 G1 中的导出子图:
- 如果 x1 与 x3 属于 H(1,3) 的不同分支,也即 x1 和 x3 之间不存在只由 1 和 3 着色的点构成的路,则通过交换含 x1 的分支中的着色顺序,可以得到 G1 的新正常点着色方案,使得 x1 和 x3 着同色,于是由情形 1,可以得到 G 的 5-正常顶点着色方案。
-
如果 x1 和 x3 属于同一个分支,否则将会得到 H(1,3) 和 H(2,4) 的交点,不满足平面图的定义。因此,基于上面的结论,π 可以扩充为 G 的 5 正常顶点着色。
Figure 4: 属于同个分支的情况