图的分数边着色
字数 3853 2025-12-08 08:14:26

图的分数边着色

我们接下来要讲解一个图论中关于边着色的精妙推广，它放宽了对每条边必须着单一颜色这一传统限制，允许“分数”分配。我们先从最基础的边着色定义开始，一步步引入分数的概念，并探讨其意义、计算方法和重要结论。

第一步：回顾经典边着色（边着色数）

  1. 核心定义：图 \(G = (V, E)\) 的正常边着色是指为每条边分配一种颜色，使得共用同一顶点的任意两条边颜色不同。所需要的最少颜色数，称为边色数，记作 \(\chi'(G)\)。
  2. 一个关键定理：维津（Vizing）定理指出，对于简单图 \(G\)，其边色数满足 \(\Delta(G) \le \chi'(G) \le \Delta(G) + 1\)。其中 \(\Delta(G)\) 是图的最大度。满足 \(\chi'(G) = \Delta(G)\) 的图称为第一类图，满足 \(\chi'(G) = \Delta(G) + 1\) 的图称为第二类图。

第二步：从“整数”到“分数”的动机与定义
经典边着色要求每条边必须完整地使用一种颜色。分数边着色放松了这一限制：

  1. 核心思想：我们可以允许使用一个颜色集合 \(\mathcal{C}\)。每条边 \(e\) 可以被分配这个集合中的多个颜色，但要求分配给它的颜色组合的总“量”为 1。同时，每个顶点 \(v\) 上，所有与 \(v\) 关联的边所分配到的同一种颜色的总量之和不能超过 1。
  2. 正式定义：图 \(G\) 的分数边着色是一个非负实数对 \((w_c)_{c \in \mathcal{C}}\) 的集合，其中每个 \(w_c\) 表示“颜色 \(c\) 的权重”，满足以下两个条件：
  • 对每条边 \(e \in E\)：所有包含边 \(e\) 的颜色 \(c\) 的权重之和 \(\sum_{c: e \in c} w_c = 1\)。（确保边被“完全着色”）
  • 对每个顶点 \(v \in V\) 和每种颜色 \(c \in \mathcal{C}\)：最多有一条与 \(v\) 关联的边被分配了颜色 \(c\)（即权重为正），或者说，颜色 \(c\) 在顶点 \(v\) 处的总权重不超过 1。这等价于：着同一种颜色的边必须构成一个匹配（即一组没有公共顶点的边）。
  1. 分数边色数：所有可行分数边着色方案中，使用的颜色权重之和 \(\sum_{c \in \mathcal{C}} w_c\) 的最小值，称为分数边色数，记作 \(\chi'_f(G)\)。

第三步：理解定义与经典着色的关系

  1. 特例：如果要求所有权重 \(w_c\) 只能是 0 或 1，那么每条边恰好属于一个颜色（匹配），每个颜色就是一个匹配，且所有匹配的并覆盖所有边。这就是经典的边着色，其色数 \(\chi'(G)\) 就是覆盖 \(E(G)\) 所需匹配的最小数量。
  2. 分数化优势：允许权重为分数（如 1/2, 1/3 等）后，我们可以更“经济”地使用颜色。例如，一个颜色（匹配）的权重可以是 0.5，意味着它只“承担”了边的一半着色任务，另一半由其他颜色承担。这通常能降低总的权重和 \(\sum w_c\)。
  3. 一个简单例子：考虑一个三角形 \(C_3\)（三个顶点两两相连）。
  • 经典边着色：由于最大度 \(\Delta = 2\)，但它是奇环，是第二类图，所以 \(\chi'(C_3) = 3\)。
  • 分数边着色：我们可以用三个匹配（每条边本身就是一个匹配），每个匹配分配权重 1/2。那么每条边恰好在两个匹配中出现，每个匹配的权重为 1/2，所以每条边获得的总权重是 \(1/2 + 1/2 = 1\)。在每个顶点，对于任意一个匹配（颜色），最多只有一条关联边属于它，且权重为 1/2，所以该颜色在该顶点处的总权重为 1/2，没有超过 1。总权重和为 \(3 \times (1/2) = 1.5\)。因此 \(\chi'_f(C_3) = 1.5\)。这小于经典的 3。

第四步：分数边着色的线性规划刻画与对偶
这是理解分数边色数性质的核心工具。

  1. 原始线性规划 (P)：分数边色数等价于以下线性规划的最优值：

\[ \text{最小化} \quad \sum_{M \in \mathcal{M}} x_M \quad \text{满足} \quad \begin{cases} \sum_{M: e \in M} x_M \ge 1, & \forall e \in E, \\ x_M \ge 0, & \forall M \in \mathcal{M}. \end{cases} \]

其中 \(\mathcal{M}\) 是图 \(G\) 中所有匹配的集合，变量 \(x_M\) 对应匹配 \(M\) 的权重。约束条件保证了每条边至少被总权重为 1 的匹配覆盖（由于目标是最小化，最优解中会精确等于 1）。
2. 对偶线性规划 (D)：根据线性规划对偶定理，其对偶规划为：

\[ \text{最大化} \quad \sum_{e \in E} y_e \quad \text{满足} \quad \begin{cases} \sum_{e \in M} y_e \le 1, & \forall M \in \mathcal{M}, \\ y_e \ge 0, & \forall e \in E. \end{cases} \]

这个对偶问题有一个很好的组合解释：为每条边 \(e\) 分配一个非负权重 \(y_e\)，使得每一个匹配 \(M\) 中所有边的权重和不超过 1。目标是最大化所有边的总权重。

第五步：分数边色数的重要性质与定理

  1. 与最大度的关系：与维津定理的分数版本对应，有 \(\chi'_f(G) \ge \Delta(G)\)。更准确地说，由线性规划对偶的强对偶定理，可以证明 \(\chi'_f(G)\) 等于另一个称为“分数边覆盖数”的参数的线性规划松弛的最优值。一个重要结论是：

\[ \chi'_f(G) = \max \left\{ \Delta(G), \max_{H \subseteq G, |V(H)| \ge 2} \frac{|E(H)|}{\lfloor |V(H)|/2 \rfloor} \right\} \]

这个最大化子图 \(H\) 的条件，来源于对偶规划最优解的结构分析，它衡量了图中边的“稠密”程度。
2. 与分数团覆盖数的关系：分数边着色可以转化为线图 \(L(G)\) 的分数团覆盖问题。图 \(G\) 的边对应线图的顶点，\(G\) 中共享一个顶点的边集对应线图中的一个团。覆盖 \(E(G)\) 的匹配对应覆盖 \(L(G)\) 顶点的团。因此，\(\chi'_f(G)\) 等于其线图 \(L(G)\) 的分数团覆盖数。
3. 有理数性质：由于线性规划系数矩阵是全幺模的（如果图是二部图）或更一般的性质，分数边色数 \(\chi'_f(G)\) 总是有理数。并且，存在一个最优解，其中所有权重 \(x_M\) 都是有理数。
4. 与经典边色数的关系：显然有 \(\chi'_f(G) \le \chi'(G)\)。由整数性间隙的研究可知，对于任意图 \(G\)，有 \(\chi'(G) \le \lceil 2 \chi'_f(G) \rceil - 1\)。这是一个非平凡的界，表明分数色数为经典色数提供了一个良好的下界和近似。

第六步：计算复杂性与应用

  1. 计算复杂性：尽管分数边色数定义为线性规划的最优值，但该线性规划的变量数（所有匹配的数量）是指数级的。然而，由于其对偶规划只有 \(|E|\) 个变量，但约束条件（对每一个匹配）是指数级的，我们可以使用椭球法或组合算法在多项式时间内求解，通过分离预言机来解决对偶规划中“约束是否被违反”的问题（即，给定边权重 \(y_e\)，是否存在匹配 \(M\) 使得 \(\sum_{e \in M} y_e > 1\)？这等价于在边权为 \(y_e\) 的图上求最大权匹配，存在多项式算法）。
  2. 应用意义：分数边着色模型在调度和资源分配问题中非常有用。例如，将边视为需要处理的任务，顶点视为资源（如处理器），颜色对应时间片。任务（边）可能需要多个不冲突的时间片（匹配）来完成，分数着色可以更灵活地安排任务，最小化总时间片数。它也常作为解决经典边着色问题的有力松弛工具，用于设计近似算法或证明下界。

总结：
图的分数边着色是经典边着色的自然推广，它通过将颜色权重从整数松弛到非负实数，得到一个更小、理论上更易处理的参数 \(\chi'_f(G)\)。它可以通过线性规划及其对偶来精确刻画，与图的最大度和稠密子图结构密切相关。虽然定义涉及指数级数量的匹配，但其值可以在多项式时间内计算。它在理论上揭示了边着色问题的深层结构，在应用中提供了更灵活的调度模型。

图的分数边着色 我们接下来要讲解一个图论中关于边着色的精妙推广，它放宽了对每条边必须着单一颜色这一传统限制，允许“分数”分配。我们先从最基础的边着色定义开始，一步步引入分数的概念，并探讨其意义、计算方法和重要结论。 第一步：回顾经典边着色（边着色数） 核心定义 ：图 \( G = (V, E) \) 的 正常边着色 是指为每条边分配一种颜色，使得 共用同一顶点的任意两条边颜色不同 。所需要的最少颜色数，称为 边色数 ，记作 \( \chi'(G) \)。 一个关键定理 ：维津（Vizing）定理指出，对于简单图 \( G \)，其边色数满足 \( \Delta(G) \le \chi'(G) \le \Delta(G) + 1 \)。其中 \( \Delta(G) \) 是图的最大度。满足 \( \chi'(G) = \Delta(G) \) 的图称为 第一类图 ，满足 \( \chi'(G) = \Delta(G) + 1 \) 的图称为 第二类图 。 第二步：从“整数”到“分数”的动机与定义 经典边着色要求每条边必须完整地使用一种颜色。分数边着色放松了这一限制： 核心思想 ：我们可以允许使用一个颜色集合 \( \mathcal{C} \)。 每条边 \( e \) 可以被分配这个集合中的 多个颜色 ，但要求分配给它的颜色组合的总“量”为 1。同时， 每个顶点 \( v \) 上，所有与 \( v \) 关联的边所分配到的 同一种颜色 的总量之和不能超过 1。 正式定义 ：图 \( G \) 的 分数边着色 是一个非负实数对 \( (w_ c)_ {c \in \mathcal{C}} \) 的集合，其中每个 \( w_ c \) 表示“颜色 \( c \) 的权重”，满足以下两个条件： 对每条边 \( e \in E \)：所有包含边 \( e \) 的颜色 \( c \) 的权重之和 \( \sum_ {c: e \in c} w_ c = 1 \)。（确保边被“完全着色”） 对每个顶点 \( v \in V \) 和 每种颜色 \( c \in \mathcal{C} \)：最多有一条与 \( v \) 关联的边被分配了颜色 \( c \)（即权重为正），或者说，颜色 \( c \) 在顶点 \( v \) 处的总权重不超过 1。这等价于：着同一种颜色的边必须构成一个 匹配 （即一组没有公共顶点的边）。 分数边色数 ：所有可行分数边着色方案中，使用的颜色权重之和 \( \sum_ {c \in \mathcal{C}} w_ c \) 的最小值，称为 分数边色数 ，记作 \( \chi'_ f(G) \)。 第三步：理解定义与经典着色的关系 特例 ：如果要求所有权重 \( w_ c \) 只能是 0 或 1，那么每条边恰好属于一个颜色（匹配），每个颜色就是一个匹配，且所有匹配的并覆盖所有边。这就是经典的 边着色 ，其色数 \( \chi'(G) \) 就是覆盖 \( E(G) \) 所需匹配的最小数量。 分数化优势 ：允许权重为分数（如 1/2, 1/3 等）后，我们可以更“经济”地使用颜色。例如，一个颜色（匹配）的权重可以是 0.5，意味着它只“承担”了边的一半着色任务，另一半由其他颜色承担。这通常能降低总的权重和 \( \sum w_ c \)。 一个简单例子 ：考虑一个三角形 \( C_ 3 \)（三个顶点两两相连）。 经典边着色：由于最大度 \( \Delta = 2 \)，但它是奇环，是第二类图，所以 \( \chi'(C_ 3) = 3 \)。 分数边着色：我们可以用三个匹配（每条边本身就是一个匹配），每个匹配分配权重 1/2。那么每条边恰好在两个匹配中出现，每个匹配的权重为 1/2，所以每条边获得的总权重是 \( 1/2 + 1/2 = 1 \)。在每个顶点，对于任意一个匹配（颜色），最多只有一条关联边属于它，且权重为 1/2，所以该颜色在该顶点处的总权重为 1/2，没有超过 1。总权重和为 \( 3 \times (1/2) = 1.5 \)。因此 \( \chi'_ f(C_ 3) = 1.5 \)。这小于经典的 3。 第四步：分数边着色的线性规划刻画与对偶 这是理解分数边色数性质的核心工具。 原始线性规划 (P) ：分数边色数等价于以下线性规划的最优值： \[ \text{最小化} \quad \sum_ {M \in \mathcal{M}} x_ M \quad \text{满足} \quad \begin{cases} \sum_ {M: e \in M} x_ M \ge 1, & \forall e \in E, \\ x_ M \ge 0, & \forall M \in \mathcal{M}. \end{cases} \] 其中 \( \mathcal{M} \) 是图 \( G \) 中所有匹配的集合，变量 \( x_ M \) 对应匹配 \( M \) 的权重。约束条件保证了每条边至少被总权重为 1 的匹配覆盖（由于目标是最小化，最优解中会精确等于 1）。 对偶线性规划 (D) ：根据线性规划对偶定理，其对偶规划为： \[ \text{最大化} \quad \sum_ {e \in E} y_ e \quad \text{满足} \quad \begin{cases} \sum_ {e \in M} y_ e \le 1, & \forall M \in \mathcal{M}, \\ y_ e \ge 0, & \forall e \in E. \end{cases} \] 这个对偶问题有一个很好的组合解释：为每条边 \( e \) 分配一个非负权重 \( y_ e \)，使得 每一个匹配 \( M \) 中所有边的权重和不超过 1。目标是最大化所有边的总权重。 第五步：分数边色数的重要性质与定理 与最大度的关系 ：与维津定理的分数版本对应，有 \( \chi'_ f(G) \ge \Delta(G) \)。更准确地说，由线性规划对偶的强对偶定理，可以证明 \( \chi'_ f(G) \) 等于另一个称为“分数边覆盖数”的参数的线性规划松弛的最优值。一个重要结论是： \[ \chi' f(G) = \max \left\{ \Delta(G), \max {H \subseteq G, |V(H)| \ge 2} \frac{|E(H)|}{\lfloor |V(H)|/2 \rfloor} \right\} \] 这个最大化子图 \( H \) 的条件，来源于对偶规划最优解的结构分析，它衡量了图中边的“稠密”程度。 与分数团覆盖数的关系 ：分数边着色可以转化为线图 \( L(G) \) 的分数团覆盖问题。图 \( G \) 的边对应线图的顶点，\( G \) 中共享一个顶点的边集对应线图中的一个团。覆盖 \( E(G) \) 的匹配对应覆盖 \( L(G) \) 顶点的团。因此，\( \chi'_ f(G) \) 等于其线图 \( L(G) \) 的分数团覆盖数。 有理数性质 ：由于线性规划系数矩阵是全幺模的（如果图是二部图）或更一般的性质，分数边色数 \( \chi'_ f(G) \) 总是有理数。并且，存在一个最优解，其中所有权重 \( x_ M \) 都是有理数。 与经典边色数的关系 ：显然有 \( \chi'_ f(G) \le \chi'(G) \)。由 整数性间隙 的研究可知，对于任意图 \( G \)，有 \( \chi'(G) \le \lceil 2 \chi'_ f(G) \rceil - 1 \)。这是一个非平凡的界，表明分数色数为经典色数提供了一个良好的下界和近似。 第六步：计算复杂性与应用 计算复杂性 ：尽管分数边色数定义为线性规划的最优值，但该线性规划的变量数（所有匹配的数量）是指数级的。然而，由于其对偶规划只有 \( |E| \) 个变量，但约束条件（对每一个匹配）是指数级的，我们可以使用 椭球法 或 组合算法 在多项式时间内求解，通过 分离预言机 来解决对偶规划中“约束是否被违反”的问题（即，给定边权重 \( y_ e \)，是否存在匹配 \( M \) 使得 \( \sum_ {e \in M} y_ e > 1 \)？这等价于在边权为 \( y_ e \) 的图上求最大权匹配，存在多项式算法）。 应用意义 ：分数边着色模型在调度和资源分配问题中非常有用。例如，将边视为需要处理的任务，顶点视为资源（如处理器），颜色对应时间片。任务（边）可能需要多个不冲突的时间片（匹配）来完成，分数着色可以更灵活地安排任务，最小化总时间片数。它也常作为解决经典边着色问题的有力松弛工具，用于设计近似算法或证明下界。 总结 ： 图的 分数边着色 是经典边着色的自然推广，它通过将颜色权重从整数松弛到非负实数，得到一个更小、理论上更易处理的参数 \( \chi'_ f(G) \)。它可以通过线性规划及其对偶来精确刻画，与图的最大度和稠密子图结构密切相关。虽然定义涉及指数级数量的匹配，但其值可以在多项式时间内计算。它在理论上揭示了边着色问题的深层结构，在应用中提供了更灵活的调度模型。