图的均匀着色 在之前的词条中，你已学习过“图的均匀着色与平衡着色”、“图的均匀染色与平衡染色”等概念。为避免重复，本词条将聚焦于 均匀着色 （Uniform Coloring）在图论中的一个具体形式，侧重于 均匀着色的定义、与常规着色的区别、均匀着色的存在性问题及相关理论 ，而非之前已讨论的平衡性或算法方面。 步骤1：均匀着色的基本定义 图的均匀着色是正常顶点着色的一种强化要求。对于一个图 \(G = (V, E)\) 的正常顶点着色（相邻顶点颜色不同），如果任意两种颜色类（即染同一种颜色的顶点集合）的大小相差不超过1，则称该着色是 均匀的 （equitable 或 uniform）。 数学表述 ：设着色函数 \(c: V \to \{1, 2, \dots, k\}\) 是正常的（相邻顶点颜色不同），且对于任意两种颜色 \(i\) 和 \(j\)，满足 \(||c^{-1}(i)| - |c^{-1}(j)|| \le 1\)。此时颜色类的大小要么相等，要么仅相差1。 与常规着色的区别 ：常规着色只要求相邻顶点颜色不同，不限制各颜色类的顶点数量；均匀着色额外要求颜色类大小尽可能均衡。 例子 ：考虑一个包含5个顶点的图，用2种颜色着色。若一种颜色类有3个顶点，另一种有2个顶点，则是均匀着色（大小差1）；若一种颜色类有4个顶点，另一种有1个顶点，则不是均匀着色（大小差3）。 步骤2：均匀着色的存在性定理（Hajnal–Szemerédi 定理） 一个关键理论问题是：对于任意图 \(G\) 和任意颜色数 \(k\)，是否总存在均匀着色？答案是否定的，但有一个著名定理给出了重要条件。 Hajnal–Szemerédi 定理 （1970）：对于任意图 \(G\) 和任意整数 \(k\)，如果 \(G\) 的最大度 \(\Delta(G) \le k-1\)，则 \(G\) 存在 \(k\)-均匀着色。 最大度条件 \(\Delta(G) \le k-1\) 是充分条件，但不是必要条件。 该定理是Brooks定理（着色数 \(\chi(G) \le \Delta(G)+1\)）在均匀着色中的类比，但更强：它保证了在颜色数 \(k \ge \Delta(G)+1\) 时，不仅存在正常着色，还可以调整为均匀着色。 例子 ：设 \(G\) 是一个最大度为3的图，取 \(k=4\)。由 Hajnal–Szemerédi 定理，存在4种颜色的均匀着色，四种颜色类的大小最多相差1。 步骤3：均匀着色与图结构的联系 均匀着色不仅是一种着色方式，还与图的结构性质密切相关： 与正则图的联系 ：在正则图中，均匀着色更容易构造，因为顶点度相同有助于平衡颜色类。 与图分解的关系 ：均匀着色可视为将图顶点集划分为大小近似的独立集，这与图的顶点划分问题相关。 均匀着色的色数 ：定义均匀着色色数 \(\chi_ {eq}(G)\) 为满足均匀着色要求的最小颜色数。显然 \(\chi_ {eq}(G) \ge \chi(G)\)，但两者不一定相等。 例子 ：完全图 \(K_ n\) 的正常着色色数为 \(n\)，均匀着色色数也是 \(n\)（因为每个顶点必须颜色不同，此时各颜色类大小均为1，自然均匀）。 步骤4：均匀着色的算法与复杂性 虽然本词条不侧重算法，但需了解基本复杂性： 判定“给定图 \(G\) 和整数 \(k\)，是否存在 \(k\)-均匀着色”是 NP-完全问题（即使 \(k=3\)）。 但对于某些特殊图类（如二部图、区间图），存在多项式时间算法。 近似算法：可以通过调整正常着色得到近似均匀的着色，例如通过交换顶点颜色来平衡颜色类大小。 例子 ：对于树图，由于 \(\chi(T) \le 2\)，且最大度可能任意大，但用2种颜色着色时，可以构造均匀着色（通过适当选择根和层）。 步骤5：均匀着色的推广与应用 均匀边着色 ：类似概念可应用于边着色，要求每种颜色的边数尽可能均衡。 均匀列表着色 ：在列表着色（每个顶点有可选颜色列表）中要求颜色类大小均衡。 应用领域 ： 任务调度：将任务分配给时间槽，使各时间段任务数均衡，且冲突任务不同时执行。 资源分配：在满足约束下均衡资源使用。 例子 ：学校排课问题中，将课程安排在不同时段，避免教师或教室冲突，且各时段课程数量大致相同，可建模为均匀着色问题。 总结 均匀着色是正常着色的均衡性强化版本，其存在性由 Hajnal–Szemerédi 定理等结果保证，与图的最大度密切相关。该概念在图划分、调度问题中有实际应用，且计算上通常是困难的。与之前学过的“均匀着色与平衡着色”不同，本词条聚焦于颜色类大小的均衡性定义及其基本理论性质。