图染色方法笔记：第一章 贪心染色（1.1节）

在这本书中，我们研究如何将一个集合划分为满足某些约束条件的子集。这个问题出现在设计电路、编译计算机代码时分配寄存器、解决数独谜题和安排飞行机组等多样的情境中。所有这些问题都可以用图染色的语言来描述，其中每种颜色代表划分中的一个子集，我们的目标是最小化颜色的数量。

一般的图染色问题没有简单的答案。更准确地说，它是 NP-hard 的^[1]。因此，我们不太可能找到一个高效的算法来在任意输入图上最优地解决染色问题。这个基本的难度结果给图染色的世界投下了长长的阴影。

与许多关于生成树、连通性和匹配的问题（对于这些问题我们有能给出最优解的高效算法）形成对比的是，对于图染色，我们主要关注于证明上下界。我们还关注图的结构，集中于平面图和其他表现出某种稀疏性的图类。

一个自然的想法是逐个考虑集合中的元素，将每个元素分配给第一个不被已经分配在那里的某个元素禁止的子集。这种贪心方法的表现可能非常好，也可能非常糟糕，这取决于我们考虑元素的顺序。在这一章中，我们寻找好的顺序，并研究它们为解决染色问题的最小颜色数量提供了什么界限。

1.1 退化性、权转移和布鲁克斯定理

1.1.1 关键思想和定义

定义 1.1 一个图 \(G\) 由一个顶点集 \(V(G)\)、一个边集 \(E(G)\) 组成，每条边是一对无序的顶点，称为边的端点。（在上面的问题中，顶点是划分的元素，边是禁止在同一部分中出现的顶点对。）如果两个顶点形成一条边，则称这两个顶点相邻。对于一个图 \(G\)，我们写 \(|G|\) 来表示其顶点集的大小，\(\|G\|\) 表示其边集的大小。在图中的一条路 \(P\) 是一系列边 \(e_1\), \(\cdots\), \(e_\ell\)，使得每一对 \(e_i\) 和 \(e_{i+1}\) 都有一个共享的端点，且没有其他边 \(e_j\) 有那个端点。（我们允许 \(\ell=1\) 甚至 \(\ell=0\) 的可能性，所以 \(P\) 可能没有边。）路的端点是仅作为 \(e_1\) 和 \(e_\ell\) 端点的顶点。由路与端点 \(v_0\) 和 \(v_\ell\) 通过添加边 \(v_\ell v_0\) 形成圈。路或圈的长度是其边的数量。如果对于所有的 \(v\), \(w\in V(G)\)，存在一条在 \(G\) 中的路，其端点为 \(v\) 和 \(w\)，则图 \(G\) 是连通的。如果图的边子集不形成圈，则称图是无圈的。一个连通的无圈图是一棵树，树的不相交并集是森林。除非另有说明，所有的图都是无向的，没有环和没有平行边。这样的图是简单的。

例如，图 1.1 中的图 \(G\)（用不同的着色显示了两次）是简单的，有 \(|G| = 8\) 和 \(\|G\| = 12\)。它是连通的，但远非无圈；因此，它既不是树也不是森林。它包含许多长度从 \(0\) 到 \(7\) 的路和长度从 \(4\) 到 \(8\) 的圈（但没有其他长度的路或圈）。

一个正常的染色（或简单地说染色）给图的每个顶点分配颜色，使得相邻顶点获得不同的颜色。我们用正整数表示颜色。一个 \(k\)-染色是使用最多 \(k\) 种颜色的合适染色。图 \(G\) 是 \(k\)-可染的，如果它有 \(k\)-染色。图 \(G\) 的色数 \(\chi(G)\) 是使得 \(G\) 是 \(k\)-可染的最小的 \(k\)。\(G\) 的使用 \(\chi(G)\) 种颜色的染色是 \(G\) 的一个最优染色。

对图进行染色的一个简单方法是逐个考虑其顶点，以某种顶点顺序 \(\sigma\) 进行，给每个顶点着色，使用其邻点尚未使用的最小颜色。这是一种使用 \(\sigma\) 的贪心染色。 图 1.1 显示了使用不同顶点顺序对同一图进行的两种贪心染色。

在这本书中，我们关注染色的存在性，而不是产生它们的算法，因此我们通常将顶点顺序 \(\sigma\) 隐含起来，如我们在我们第一个命题的证明中所做的。然而，我们在 1.1.3 节 的末尾简要讨论了将存在性证明转换为高效算法的方法。（对于我们的几乎所有证明，我们都可以这样做。）

对于每个图 \(G\)，存在一个顶点顺序 \(\sigma\) ，使得使用 \(\sigma\) 对 \(G\) 进行贪心染色产生最优染色。（给定一个最优染色，通过首先列出所有着色为 \(1\) 的顶点，然后是着色为 \(2\) 的顶点，依此类推，形成 \(\sigma\) 。）但这个观察并没有提供一个高效算法，因为每个图 \(G\) 有 \(|G|!\) 可能的顶点顺序——远远超过我们尝试的所有顺序。即使对于色数为 \(2\) 的图类，一些顶点顺序的表现也很差（见 练习 1）。幸运的是，我们通常可以使用 \(G\) 的结构快速找到一个好顺序 \(\sigma\) ，尽管可能不是最优的。

命题 1.2 如果 \(G\) 是森林，则 \(\chi(G) \le 2\)。

证明. 假设命题是错误的，令 \(G\) 是一个顶点数最少的反例。由于 \(G\) 是森林，它包含一个顶点 \(v\)，其度数最多为 \(1\)。令 \(G' := G − v\)。由于 \(G'\) 也是森林，并且 \(G'\) 的顶点数少于 \(G\)，而 \(G\) 是最小的反例，所以结论对 \(G'\) 成立。也就是说，\(G'\) 有一个 \(2\) 染色 \(\varphi'\)。由于 \(\varphi'\) 在 \(v\) 的邻点上最多使用一种颜色，我们可以贪心地将染色 \(\varphi'\) 扩展到 \(G\)。因此 \(G\) 根本不是一个反例。\(\Box\)

命题 1.2

1.1.2 曲面上的图染色：海伍德界

1.1.3 权转移法和高效染色算法

1.1.4 布鲁克斯定理

\(\Box\)

1. 我们将在第 A.1 节给出了一个正式的定义。 ↩︎