【离散数学】图论 第七章(6) 图的结点着色和Welch Powell法、平面图着色、希伍德五色定理、四色定理

本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解数学知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充：

与平面图密切相关的一个重要问题是图的着色问题：

历史简介：

图的着色分为结点着色和边着色两种，下面仅介绍关于图的结点着色的概念和基本理论。

定义6.1.1 设 G = ⟨ V , E ⟩ G = \lang V, E\rang G=⟨V,E⟩ 是无向图，给图 G G G 中的每个结点指定一种颜色，若满足两个邻接的结点着色不同，则称为图 G G G 的结点正常着色 proper coloring 。如果可以用 k k k 种不同的颜色给图 G G G 的结点正常着色，则称 G G G 是结点可 k k k-着色的 k-colorable 。对图的结点正常着色所需要的最少的颜色数，称为 G G G 的顶着色数，简称为色数 chromatic number ，记为 χ ( G ) \chi (G) χ(G) 。色数为 k k k 的图称为 k k k 色图。

用韦尔奇·鲍威尔 Welch Powell 法，可对任意图 G G G 的结点进行正常着色，该方法的步骤如下：

【例1】分别对图7.6.1所示的图 G G G 和 H H H 中的结点进行正常着色。

解：（1）用韦尔奇-鲍威尔法对 G G G 进行着色，整个过程如图7.6.2所示。 首先将 G G G 中结点按照度数由大到小排序，得到序列 { b , c , d , e , f , a , g } \{ b, c, d, e, f, a, g\} {b,c,d,e,f,a,g} 。然后，将结点 b b b 着上红色，并且将与 b b b 不邻接的结点 f f f 也着上红色，注意 g g g 与 b b b 不邻接、但与 f f f 邻接， f f f 已着上红色，所以 g g g 不能着上红色；其次，将结点 c c c 着上黄色，并将与 c c c 不邻接的 e e e 着上黄色；接下来，将结点 d d d 着上蓝色，并将与 d d d 不邻接的 a a a 着上蓝色， g g g 与 d d d 和 a a a 均不邻接，因此它也可以着上蓝色。这样，整个着色过程就结束了， G G G 是可 3 3 3-着色的。 （2）对于图 H H H 可用与 G G G 同样的着色过程，只是在对结点 g g g 着色时，因为 g g g 与 a a a 邻接，所以它不能着蓝色，必须使用一种新的颜色对其着色，因此 H H H 是可 4 4 4-着色的。

利用图的色数可以解决很多现实问题，例如，学校期末考试安排各门课程的考试时间时，不能把同一位学生选修的两门课，安排在同一个时间考试。我们可将每门课程抽象为一个结点，如果两门课程有同一个学生选修，则在这两个结点间连上一条边，构成图 G G G 。如果 G G G 的色数为 k k k ，那么相同颜色的课程可以在同一时间开考，所需考试的最小次数即为 k k k 。不难发现，考试次数的上界是「学生选修的最多课程数+1」。

定理7.6.1 任何图 G = ⟨ V , E ⟩ G= \langle V, E\rangle G=⟨V,E⟩ 均满足 χ ( G ) ≤ Δ ( G ) + 1 ,   Δ ( G ) = max ⁡ { d e g ( u ) ∣ u ∈ V } \chi(G) \le \Delta(G) + 1,\ \Delta(G) = \max \{ deg(u) \mid u\in V\} χ(G)≤Δ(G)+1, Δ(G)=max{deg(u)∣u∈V} 。 定理7.6.2 无向图 G G G 的色数 χ ( G ) = 2 \chi(G) = 2 χ(G)=2 ，当且仅当 G G G 是一个二部图。 以上定理的证明留作练习。

地图着色问题，实质上就是对一个平面图中的面进行着色，它可以通过对偶图转换为与之等价的、平面图的结点着色问题。

定义7.6.2 设 G = ⟨ V , E ⟩ G = \langle V, E\rangle G=⟨V,E⟩ 是平面图， G ′ G' G′ 是 G G G 的一个平面嵌入， F ( G ′ ) F(G') F(G′) 是 G ′ G' G′ 的面集合。构造图 G ∗ G^* G∗ ，若 G ∗ G^* G∗ 的结点集合 V ( G ∗ ) = F ( G ′ ) V(G^*) = F(G') V(G∗)=F(G′) ，且任取两个结点 f 1 ,   f 2 ∈ V ( G ∗ ) f_1,\ f_2 \in V(G^*) f1​, f2​∈V(G∗) ， f 1 f_1 f1​ 和 f 2 f_2 f2​ 之间存在边 e e e 当且仅当 f 1 f_1 f1​ 和 f 2 f_2 f2​ 在 G ′ G' G′ 中有一条公共边，则称 G ∗ G^* G∗ 是 G G G 的对偶图。

求平面图 G G G 的一个平面嵌入 G ′ G' G′ 所对应的对偶图 G ∗ G^* G∗ 的一般步骤如下： （1）对于图 G G G 的每个面 r i r_i ri​ ，在 r i r_i ri​ 的内部作一个结点 v i ∗ ∈ V ( G ∗ ) v_i^* \in V(G^*) vi∗​∈V(G∗) ； （2）对于任何两个面 r i ,   r j r_i,\ r_j ri​, rj​ 的每一条公共边界 e k e_k ek​ ，都作一条与 e k e_k ek​ 相交的边 e k ∗ = { v i ∗ ,   v j ∗ } ∈ E ( G ∗ ) e^*_k = \{ v_i^*,\ v_j^*\} \in E(G^*) ek∗​={vi∗​, vj∗​}∈E(G∗) ； （3）当 e k e_k ek​ 仅是面 r i r_i ri​ 的边界时，给 v i ∗ v_i^* vi∗​ 作一条与 e k e_k ek​ 相交的自回路 e k ∗ = { v i ∗ ,   v i ∗ } ∈ E ( G ∗ ) e^*_k = \{ v_i^*,\ v_i^*\} \in E(G^*) ek∗​={vi∗​, vi∗​}∈E(G∗) 。

图7.6.3给出了由图 G G G 构造其对偶图 G ∗ G^* G∗ 的一个实例，其中，图 G G G 的结点和边分别用 ∘ \circ ∘ 和实线表示，而它的对偶图 G ∗ G^* G∗ 的结点和边分别用 ∙ \bullet ∙ 和虚线表示：

由对偶图的定义可知，一个连通平面图 G G G 的对偶图 G ∗ G^* G∗ 也是平面图， G ∗ G^* G∗ 的对偶图是 G G G ，并且一个平面图的不同平面嵌入，可能得到不同的对偶图。

1890年，希伍德就证明了，任何连通简单平面图都是可 5 5 5-着色的。下面给出其证明过程——定理7.6.3和定理7.6.4。

定理7.6.3 设 G = ⟨ V , E ⟩ G = \langle V, E\rangle G=⟨V,E⟩ 是一个连通简单平面图，且 ∣ V ∣ ≥ 3 ,   ∣ E ∣ = m |V| \ge 3,\ |E| = m ∣V∣≥3, ∣E∣=m ，则 G G G 中必存在结点 u ∈ V u \in V u∈V ，满足 d e g ( u ) ≤ 5 deg(u) \le 5 deg(u)≤5 。 证明 假设 G G G 中所有结点的度均大于等于 6 6 6 。因为 ∑ v i ∈ V d e g ( v i ) = 2 m \displaystyle \sum_{v_i \in V} deg(v_i) = 2m vi​∈V∑​deg(vi​)=2m ，故 2 m ≥ 6 ∣ V ∣ 2m \ge 6|V| 2m≥6∣V∣ ，所以 m ≥ 3 ∣ V ∣ > 3 ∣ V ∣ − 6 m \ge 3|V| > 3|V| - 6 m≥3∣V∣>3∣V∣−6 。这与定理7.5.3的结论矛盾。因此， G G G 中必存在结点 u ∈ V u \in V u∈V ，满足 d e g ( u ) ≤ 5 deg(u) \le 5 deg(u)≤5 。

定理7.6.4（希伍德五色定理）任一连通简单平面图 G = ⟨ V , E ⟩ G = \langle V, E\rangle G=⟨V,E⟩ 都是可 5 5 5-着色的。 证明 对图 G G G 中的结点数进行归纳。 （1）当 ∣ V ∣ ≤ 5 |V| \le 5 ∣V∣≤5 时，结论显然成立。 （2）假设当 ∣ V ∣ = k |V| = k ∣V∣=k 时结论成立， k ≥ 5 k \ge 5 k≥5 。 （3）考察 ∣ V ∣ = k + 1 |V| = k + 1 ∣V∣=k+1 时的情况。由引理知， G G G 中必然存在结点 u ∈ V u \in V u∈V ，满足 d e g ( u ) ≤ 5 deg(u) \le 5 deg(u)≤5 。将结点 u u u 从图中删去得到图 G − u G - u G−u 。由归纳假设知， G − u G-u G−u 可用 5 5 5 种颜色正常着色。现将 u u u 放回从而恢复原图 G G G ，分情况讨论： ① d e g ( u ) < 5 deg(u) < 5 deg(u)