图的着色与色数问题 图着色是图论中研究顶点、边或面的着色规则的一类问题，其中最经典的是 顶点着色 ：对图的每个顶点分配一种颜色，使得任意相邻顶点颜色不同。目标是使用尽可能少的颜色。 1. 基本定义与示例 正常着色 ：若相邻顶点颜色不同，则称着色是正常的。 色数 ：图 \(G\) 的色数 \(\chi(G)\) 是使其存在正常着色的最小颜色数。 示例： 树（无环连通图）的色数为 2（二分图）。 奇环（如三角形）的色数为 3。 完全图 \(K_ n\) 的色数为 \(n\)。 2. 着色的性质与简单界 上界 ： \(\chi(G) \leq \Delta(G) + 1\)，其中 \(\Delta(G)\) 是最大度（贪心着色定理）。 Brooks 定理：若 \(G\) 不是完全图或奇环，则 \(\chi(G) \leq \Delta(G)\)。 下界 ： \(\chi(G) \geq \omega(G)\)，其中 \(\omega(G)\) 是最大团的大小。 3. 着色与图结构的关系 二分图判定 ：图可 2-着色当且仅当它是二分图（无奇环）。 四色定理 ：任何平面图可 4-着色（计算机辅助证明）。 五色定理 ：平面图必满足 \(\chi(G) \leq 5\)（可用归纳法手工证明）。 4. 着色算法与复杂性 贪心算法 ：按顺序着色顶点，每次选择与已着色邻居不同的最小颜色。最坏情况需 \(\Delta+1\) 色。 复杂性 ：判定 \(\chi(G) \leq k\) 是 NP-完全问题（当 \(k \geq 3\)）。 启发式方法 ：如 Welsh-Powell 算法（按度降序着色）、DSatur 算法（动态选择饱和度高顶点）。 5. 特殊图的色数 完美图 ：\(\chi(G) = \omega(G)\) 对所有诱导子图成立（如二分图、区间图）。 平面图 ：色数 ≤ 4，但存在非 4-可着色的平面图需 4 色（如轮图 \(W_ 4\)）。 稀疏图 ：若图无 \(K_ 4\) 子图，可能仍需 4 色（如 Grötzsch 图是无三角形的 4-色图）。 6. 推广与变种 边着色 ：对边着色，使相邻边颜色不同（Vizing 定理：边色数 ≤ \(\Delta+1\)）。 列表着色 ：每个顶点只能从预设颜色列表中选择（列表色数可能大于普通色数）。 圆着色 ：颜色视为圆周上的点，相邻顶点颜色需保持一定距离（推广分数着色）。 7. 应用场景 调度问题 ：课程安排、寄存器分配（冲突关系建模为图，色数即最小资源数）。 地图着色 ：国家或区域着色（转化为对偶图的顶点着色）。 频段分配 ：无线网络中避免相邻节点频率冲突。 通过逐步理解着色规则、色数界、算法及推广，可掌握这一经典问题的核心思想与实用价值。