基于线性规划的图边染色（Edge Coloring）问题的线性规划模型与舍入算法求解示例
字数 7983 2025-12-14 14:52:54

基于线性规划的图边染色（Edge Coloring）问题的线性规划模型与舍入算法求解示例

1. 问题描述

我们考虑经典的图边染色（Edge Coloring）问题。给定一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集合，\(E\) 是边集合。目标是用尽可能少的颜色给图中的每条边染色，使得共享同一个顶点的任意两条边（即相邻边）颜色不同。所需的最少颜色数称为图的边色数（Edge Chromatic Number）或色指数（Chromatic Index）。这是一个组合优化问题，在图论和调度等领域有广泛应用。

问题形式化：找到一个从边集 \(E\) 到颜色集合 \(\{1, 2, ..., k\}\) 的映射，使得任意两条相邻边颜色不同，并最小化颜色数 \(k\)。

重要背景：

  • 根据Vizing定理，任意简单无向图的边色数要么等于其最大度数 \(\Delta\)，要么等于 \(\Delta + 1\)。
  • 然而，确定一个图究竟是第1类（边色数为 \(\Delta\)）还是第2类（边色数为 \(\Delta + 1\)）是NP-hard的。
  • 对于一般图，边染色问题是NP-hard的，但存在近似算法。

本题我们将用线性规划（LP）松弛和随机舍入技术，为边染色问题设计一个近似算法，并分析其近似比。

2. 线性规划建模

关键思想：将边染色问题表达为一个整数线性规划（ILP），然后松弛为线性规划（LP）。我们引入变量来指示“边e是否被染成颜色c”。

定义参数：

  • 设最大可能的颜色数为 \(K\)。根据Vizing定理，我们知道 \(\Delta \le \text{边色数} \le \Delta + 1\)。但为了建模，我们可以取一个上界，例如 \(K = |E|\)（最坏情况每条边颜色不同）。但更紧的上界是 \(2\Delta - 1\)（通过简单贪婪算法可得）。不过，我们可以先设 \(K\) 为一个足够大的数，然后通过线性规划来确定实际需要的颜色数。
  • 更常见的建模方式是不预设颜色数量K，而是用分数变量表示“边e使用颜色c的比例”，然后最小化使用的颜色总数。为此，我们可以引入一个二元变量 \(y_c\) 表示颜色c是否被使用，再引入变量 \(x_{e,c}\) 表示边e是否被染成颜色c。

更紧凑的建模（基于分数边染色）：考虑线性规划松弛的直接形式，其最优解的值称为分数边色数 \(\chi'_f(G)\)。已知 \(\Delta \le \chi'_f(G) \le \chi'(G) \le \Delta + 1\)。

我们可以构造如下线性规划（LP）：

  • 变量：对每条边 \(e \in E\) 和每种颜色 \(c \in \{1, ..., K\}\)，定义变量 \(x_{e,c} \in [0, 1]\)，表示边e被赋予颜色c的程度（分数）。
  • 约束：
    1. 每条边必须被完全染色：对每条边 \(e\)，有 \(\sum_{c=1}^{K} x_{e,c} = 1\)。
    2. 每个顶点上，每种颜色至多使用一次（因为相邻边颜色不能相同）：对每个顶点 \(v\) 和每种颜色 \(c\)，有 \(\sum_{e \in \delta(v)} x_{e,c} \le 1\)，其中 \(\delta(v)\) 是与顶点v关联的边集合。
  • 目标：最小化使用的颜色总数，即 \(\sum_{c=1}^{K} y_c\)，其中 \(y_c\) 是0-1变量表示颜色c是否被使用。但这里我们无法直接最小化颜色数，因为颜色索引c是预先给定的。

替代建模：我们可以用另一种等价的线性规划，其目标是最小化一个实数t，使得存在分数染色满足每个顶点上所有颜色的总使用量不超过t。这个t可以看作是所需颜色数的分数下界。具体来说，考虑以下线性规划（称为“分数边染色LP”）：

变量：对每条边 \(e\)，定义一个分数向量 \(x_e \in [0, 1]^C\)，其中C是一个足够大的颜色集（例如大小 \(|E|\)）。但更常见的是，我们考虑对每个顶点v，与v关联的边分配给颜色c的总和不超过1，而目标是最小化一个公共的上界t，使得存在分数分配满足：

\[\begin{aligned} \text{minimize} \quad & t \\ \text{subject to} \quad & \sum_{c} x_{e,c} = 1, \quad \forall e \in E \\ & \sum_{e \in \delta(v)} x_{e,c} \le t, \quad \forall v \in V, \forall c \\ & x_{e,c} \ge 0, \quad \forall e \in E, \forall c \end{aligned} \]

这里颜色c的索引范围是所有正整数，但实际上在LP中，我们可以将颜色c限制在1到|E|。注意，在这个LP中，t是一个变量，表示每种颜色在每个顶点上的“容量”。如果t=1，意味着我们可以将边集合划分成若干个匹配（每种颜色对应一个匹配），这正是边染色的定义。因此，上述LP的最优值 \(t^*\) 是分数边色数 \(\chi'_f(G)\) 的定义之一。已知 \(\chi'_f(G) \ge \Delta\)，并且 \(\chi'_f(G)\) 可以通过求解上述LP得到。

实际求解的LP形式：为了便于求解，我们固定颜色数 \(K\) 为一个足够大的数（比如 \(K = |E|\) 或 \(2\Delta\)），并直接求解以下线性规划，然后通过舍入得到整数解。但更常见的近似算法方法是：先求解上述关于t的LP得到最优值 \(t^*\)，然后通过某种舍入过程构造一个整数边染色，使用的颜色数最多为 \(\lceil t^* \rceil + 1\) 或 \(\lceil t^* \rceil + O(1)\)。然而，这需要复杂的随机舍入和修正步骤。

为简化讲解，我们采用另一种常见的整数规划松弛，然后进行随机舍入，并分析近似比。具体模型如下：

设颜色集合为 \(\{1, 2, ..., K\}\)，其中 \(K\) 是某个足够大的数（比如 \(2\Delta\)）。我们引入0-1变量：

  • \(y_c = 1\) 如果颜色c被使用，否则为0。
  • \(x_{e,c} = 1\) 如果边e被染成颜色c，否则为0。

整数规划（IP）为：

\[\begin{aligned} \text{minimize} \quad & \sum_{c=1}^{K} y_c \\ \text{subject to} \quad & \sum_{c=1}^{K} x_{e,c} = 1, \quad \forall e \in E \\ & \sum_{e \in \delta(v)} x_{e,c} \le 1, \quad \forall v \in V, \forall c \\ & x_{e,c} \le y_c, \quad \forall e \in E, \forall c \\ & x_{e,c} \in \{0,1\}, \quad y_c \in \{0,1\}. \end{aligned} \]

约束解释：

  1. 每条边必须被分配恰好一种颜色。
  2. 在每个顶点v上，每种颜色至多被分配给一条关联边（相邻边不同色）。
  3. 如果颜色c没有被使用（\(y_c=0\)），则任何边都不能被染成颜色c。

线性规划松弛：将 \(x_{e,c}\) 和 \(y_c\) 松弛到 [0,1] 区间，得到LP。设LP的最优值为 \(OPT_{LP}\)。显然 \(OPT_{LP} \le \chi'(G)\)（整数规划最优值）。

3. 求解线性规划松弛

我们可以用任何线性规划求解器（例如单纯形法、内点法）求解上述LP。求解后得到分数解 \(x_{e,c}^*, y_c^*\)。注意到，由于约束 \(\sum_{c} x_{e,c} = 1\)，且每个顶点-颜色对的和 ≤ 1，我们可以推导出 \(OPT_{LP} \ge \Delta\)，因为每个顶点的度数至少为 \(\Delta\) 的顶点，其关联边的颜色分配总和至少为 \(\Delta\)，而每种颜色在每个顶点上贡献至多1，所以至少需要 \(\Delta\) 种颜色（分数意义上）。实际上，可以证明 \(OPT_{LP} = \chi'_f(G)\)，且满足 \(\Delta \le \chi'_f(G) \le \chi'(G) \le \Delta + 1\)。

算法步骤1：求解LP松弛，得到最优解 \((x^*, y^*)\)。设 \(t^* = \sum_c y_c^*\)（分数颜色数）。事实上，由于 \(y_c^*\) 是分数，这个和可能不是整数，但可以证明 \(t^* = \chi'_f(G)\)。

4. 随机舍入与冲突处理

现在我们有一个分数解 \(x_{e,c}^*\)。我们需要将其舍入为一个整数解（即一个合法的边染色）。一个自然的想法是随机舍入：对每条边e，我们根据分布 \(\{ x_{e,c}^* \}\) 独立地随机选择一种颜色c。但这样会导致冲突：一个顶点上可能有多条边被赋予了相同颜色，违反相邻边不同色的约束。

如何解决冲突？我们可以采用以下步骤：

  1. 随机舍入：对每条边e，独立地以概率 \(x_{e,c}^*\) 将其“临时”分配给颜色c。注意，由于 \(\sum_c x_{e,c}^* = 1\)，这是一个概率分布。
  2. 冲突检测：对于每个顶点v和每种颜色c，检查v的关联边中有多少条被分配了颜色c。如果超过1条，则发生冲突。
  3. 冲突解决：我们需要重新分配冲突边的颜色，使得每个顶点-颜色对最多只有一条边。一种方法是：对于每个顶点v，如果有多条边被赋予颜色c，我们只保留其中一条（随机选择），其他边标记为“未着色”。然后，对未着色的边，重新进行染色，但这个过程可能复杂，且可能导致颜色数增加。

更系统的舍入方法：我们可以将分数解 \(x_{e,c}^*\) 视为一个“概率分布”，然后尝试为每条边分配颜色，使得每个顶点上每种颜色至多出现一次。这实际上是一个匹配问题：对于每种颜色c，考虑子图 \(H_c\)，其中顶点集为V，边集为被赋予颜色c的边（在舍入后）。我们希望 \(H_c\) 是一个匹配（即每个顶点度数 ≤ 1）。但随机舍入后， \(H_c\) 可能不是匹配。

标准技巧：利用劳瓦尔局部引理（Lovász Local Lemma, LLL） 或条件概率法 来构造一个无冲突的舍入。但这里我们描述一个更简单的迭代随机舍入方法，它基于以下观察：

分数解 \(x^*\) 满足每个顶点v上，所有边和所有颜色的总和为 \(\sum_{e \in \delta(v)} \sum_c x_{e,c}^* = |\delta(v)|\)。同时，对每个顶点v和每种颜色c，有 \(\sum_{e \in \delta(v)} x_{e,c}^* \le 1\)。这意味着向量 \((x_{e,c}^*)\) 可以看作是“边-颜色对”上的一个分数匹配，其中每个顶点-颜色对是一个“资源”，每个边是一个“任务”。

我们可以将问题转化为超图匹配的舍入。已知有结果：上述线性规划的分数解可以通过舍入得到一个整数解，使用的颜色数最多为 \(\lceil t^* \rceil + 1\)。具体算法如下：

  • 设 \(t = \lceil t^* \rceil\)。
  • 我们准备 \(t+1\) 种颜色。目标是用这 \(t+1\) 种颜色构造一个合法的边染色。
  • 从分数解 \(x^*\) 出发，我们为每条边e独立地随机选择一种颜色c，但选择概率为 \(x_{e,c}^* / t^*\) 的调整？这里需要小心，因为 \(\sum_c x_{e,c}^* = 1\)，而 \(t^* \ge 1\)。如果我们简单地以概率 \(x_{e,c}^*\) 选择颜色c，那么每种颜色c被选中的概率为 \(y_c^*\)，而 \(\sum_c y_c^* = t^*\)。但我们需要确保每条边只选一种颜色，且每个顶点上每种颜色至多出现一次。

实际上，有一个经典的舍入算法：

  1. 求解LP，得到 \(x^*\)。
  2. 对于每条边e，定义其颜色列表 \(L_e = \{ c : x_{e,c}^* > 0 \}\)。
  3. 对于每个顶点v，以及每种颜色c，定义“容量”为1。
  4. 这是一个列表边染色问题，其中每个边有一个颜色列表，每个顶点-颜色对有容量限制。
  5. 已知如果每个列表大小至少为 \(t+1\)，且每个颜色在顶点v的关联边的列表中出现次数不超过某个界，则可以找到可行染色。在我们的LP解中，每个边e的列表大小期望至少为1，但可能需要扩展。

更实用的方法：由于边色数的近似算法有已知结果，我们可以直接利用以下事实：存在多项式时间算法，能够用 \(\Delta + 1\) 种颜色边染色任何简单图。这已经是Vizing定理的构造性证明给出的算法。但如果我们想基于LP舍入得到一个近似比略大于1的算法，可以采用以下步骤：

  • 求解LP得到 \(t^*\)。
  • 令 \(k = \lceil t^* \rceil + 1\)。由于 \(t^* \ge \Delta\)，我们有 \(k \le \Delta + 2\)（因为 \(t^* \le \Delta + 1\)，所以 \(k \le \Delta + 2\)）。
  • 然后，利用多项式时间算法（如二分图边染色算法）为原图构造一个 \(k\) 种颜色的边染色。具体地，我们可以将原图转化为线图，则边染色问题转化为线图的顶点染色问题。然后使用顶点染色的近似算法（如基于半定规划的舍入算法）对线图进行顶点染色，可以得到使用大约 \(1.1 \chi\) 种颜色的染色，其中 \(\chi\) 是线图的色数（即原图的边色数）。但线图的顶点度数可能很大，导致近似比变差。

为了保持简单，我们给出一个基于LP舍入的简单随机算法思路，并分析其期望性能：

算法步骤：

  1. 求解LP，得到最优解 \(x_{e,c}^*\) 和 \(t^* = \sum_c y_c^*\)。
  2. 令颜色数 \(k = \lceil t^* \rceil + 1\)。
  3. 构造一个随机边染色如下：
    • 初始化所有边未染色。
    • 对每种颜色 \(c = 1, 2, ..., k\)，执行以下操作：
      a. 根据分数解 \(x^*\)，以概率 \(x_{e,c}^*\) 将边e加入颜色c的候选集合（独立地对每条边进行）。
      b. 对于每个顶点v，如果有多条关联边在候选集合中，则只保留其中一条（随机选择），其余从候选集合中移除。
      c. 将候选集合中的边正式染成颜色c，并标记为已染色。
    • 对未染色的边，递归地重复此过程（用剩余的颜色）。

算法分析：可以证明，经过一轮（k种颜色）后，每条边以常数概率被染色。重复对数轮后，所有边都能被染色。最终使用的颜色数为 \(O(k \log n)\)，但这不是一个紧的界。

实际上，已知存在更精巧的舍入方法，可以得到使用 \(\lceil t^* \rceil + 1\) 种颜色的边染色。这需要利用整数分解定理（因为分数边染色多面体是匹配多面体的张量积，其整数间隙为1）。但证明较复杂，超出了本示例的范围。

5. 示例演示

考虑一个简单图：三角形（3个顶点，3条边）。最大度数 \(\Delta = 2\)。已知三角形是奇环，其边色数为3（即 \(\Delta+1\)）。

建立LP：设颜色数上界 \(K=3\)。变量：\(x_{e1,c}, x_{e2,c}, x_{e3,c}\) 对于三条边和3种颜色，以及 \(y_1, y_2, y_3\)。

约束：

  • 每条边颜色和=1。
  • 每个顶点-颜色对：例如顶点v1关联边e1,e2，对颜色1：\(x_{e1,1} + x_{e2,1} \le 1\)。
  • \(x_{e,c} \le y_c\)。

目标：最小化 \(y_1+y_2+y_3\)。

求解LP（例如单纯形法），得到最优解：每条边均匀分配三种颜色，即 \(x_{e,c}^* = 1/3\) 对所有e,c，且 \(y_c^* = 1/3\)。目标值 \(OPT_{LP} = 1\)。这小于整数最优值3，说明松弛间隙很大。但注意，我们这里使用的K=3可能太小，导致LP松弛不紧。实际上，分数边色数 \(\chi'_f\) 对于三角形是2（因为可以给每条边分配两种颜色各1/2），但我们这里建模中K=3，且约束 \(x_{e,c} \le y_c\) 导致 \(y_c\) 必须 ≥ 每条边的颜色c的分数，所以 \(y_c\) 至少为1/3，总和至少为1。若我们使用更一般的分数边染色LP（最小化t的那个），可以得到 \(t^* = 1.5\)（因为每条边分给两种颜色各1/2，每个顶点上每种颜色总和为1）。这更接近真实分数色数。

舍入：从分数解出发，我们可以采用随机舍入。例如，对每条边，以1/2概率选颜色1，1/2概率选颜色2。但可能产生冲突（一个顶点有两条边同色）。我们可以重新分配冲突的边，最终可能需要3种颜色。实际上，三角形必须用3种颜色，所以舍入后得到3种颜色，而 \(t^*=1.5\)，所以 \(\lceil t^* \rceil + 1 = 3\)，这正是最优解。

6. 总结

  • 边染色问题可以用线性规划松弛来建模，其分数最优值 \(\chi'_f(G)\) 满足 \(\Delta \le \chi'_f(G) \le \chi'(G) \le \Delta + 1\)。
  • 通过求解LP并舍入，可以构造一个使用最多 \(\lceil \chi'_f(G) \rceil + 1\) 种颜色的边染色，这意味着最多使用 \(\Delta + 2\) 种颜色。但已知Vizing定理的构造性算法可以达到 \(\Delta + 1\) 种颜色，所以LP舍入算法的主要理论意义在于提供了分数下界，并可以扩展到更复杂的约束（如列表边染色）。
  • 这个示例展示了如何将组合优化问题建模为整数线性规划，通过线性规划松弛获得下界，并设计舍入算法得到近似解。
基于线性规划的图边染色（Edge Coloring）问题的线性规划模型与舍入算法求解示例 1. 问题描述 我们考虑经典的 图边染色（Edge Coloring） 问题。给定一个 无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集合，\( E \) 是边集合。目标是用尽可能少的颜色给图中的每条边染色，使得 共享同一个顶点的任意两条边（即相邻边）颜色不同 。所需的最少颜色数称为图的 边色数 （Edge Chromatic Number）或 色指数 （Chromatic Index）。这是一个组合优化问题，在图论和调度等领域有广泛应用。 问题形式化 ：找到一个从边集 \( E \) 到颜色集合 \( \{1, 2, ..., k\} \) 的映射，使得任意两条相邻边颜色不同，并最小化颜色数 \( k \)。 重要背景 ： 根据 Vizing定理 ，任意简单无向图的边色数要么等于其最大度数 \( \Delta \)，要么等于 \( \Delta + 1 \)。 然而，确定一个图究竟是第1类（边色数为 \( \Delta \)）还是第2类（边色数为 \( \Delta + 1 \)）是NP-hard的。 对于 一般图 ，边染色问题是NP-hard的，但存在近似算法。 本题我们将用 线性规划（LP）松弛 和 随机舍入 技术，为边染色问题设计一个近似算法，并分析其近似比。 2. 线性规划建模 关键思想 ：将边染色问题表达为一个 整数线性规划（ILP） ，然后松弛为线性规划（LP）。我们引入变量来指示“边e是否被染成颜色c”。 定义参数 ： 设最大可能的颜色数为 \( K \)。根据Vizing定理，我们知道 \( \Delta \le \text{边色数} \le \Delta + 1 \)。但为了建模，我们可以取一个上界，例如 \( K = |E| \)（最坏情况每条边颜色不同）。但更紧的上界是 \( 2\Delta - 1 \)（通过简单贪婪算法可得）。不过，我们可以先设 \( K \) 为一个足够大的数，然后通过线性规划来确定实际需要的颜色数。 更常见的建模方式是 不预设颜色数量K ，而是用分数变量表示“边e使用颜色c的比例”，然后最小化使用的颜色总数。为此，我们可以引入一个二元变量 \( y_ c \) 表示颜色c是否被使用，再引入变量 \( x_ {e,c} \) 表示边e是否被染成颜色c。 更紧凑的建模（基于分数边染色） ：考虑线性规划松弛的直接形式，其最优解的值称为 分数边色数 \( \chi'_ f(G) \)。已知 \( \Delta \le \chi'_ f(G) \le \chi'(G) \le \Delta + 1 \)。 我们可以构造如下线性规划（LP）： 变量：对每条边 \( e \in E \) 和每种颜色 \( c \in \{1, ..., K\} \)，定义变量 \( x_ {e,c} \in [ 0, 1 ] \)，表示边e被赋予颜色c的程度（分数）。 约束： 每条边必须被完全染色 ：对每条边 \( e \)，有 \( \sum_ {c=1}^{K} x_ {e,c} = 1 \)。 每个顶点上，每种颜色至多使用一次 （因为相邻边颜色不能相同）：对每个顶点 \( v \) 和每种颜色 \( c \)，有 \( \sum_ {e \in \delta(v)} x_ {e,c} \le 1 \)，其中 \( \delta(v) \) 是与顶点v关联的边集合。 目标：最小化使用的颜色总数，即 \( \sum_ {c=1}^{K} y_ c \)，其中 \( y_ c \) 是0-1变量表示颜色c是否被使用。但这里我们无法直接最小化颜色数，因为颜色索引c是预先给定的。 替代建模 ：我们可以用另一种等价的线性规划，其 目标是最小化一个实数t ，使得存在分数染色满足每个顶点上所有颜色的总使用量不超过t。这个t可以看作是所需颜色数的分数下界。具体来说，考虑以下线性规划（称为“分数边染色LP”）： 变量：对每条边 \( e \)，定义一个 分数向量 \( x_ e \in [ 0, 1 ]^C \)，其中C是一个足够大的颜色集（例如大小 \( |E| \)）。但更常见的是，我们考虑对每个顶点v，与v关联的边分配给颜色c的总和不超过1，而目标是最小化一个公共的上界t，使得存在分数分配满足： \[ \begin{aligned} \text{minimize} \quad & t \\ \text{subject to} \quad & \sum_ {c} x_ {e,c} = 1, \quad \forall e \in E \\ & \sum_ {e \in \delta(v)} x_ {e,c} \le t, \quad \forall v \in V, \forall c \\ & x_ {e,c} \ge 0, \quad \forall e \in E, \forall c \end{aligned} \] 这里颜色c的索引范围是所有正整数，但实际上在LP中，我们可以将颜色c限制在1到|E|。注意，在这个LP中，t是一个变量，表示每种颜色在每个顶点上的“容量”。如果t=1，意味着我们可以将边集合划分成若干个匹配（每种颜色对应一个匹配），这正是边染色的定义。因此，上述LP的最优值 \( t^* \) 是分数边色数 \( \chi'_ f(G) \) 的定义之一。已知 \( \chi'_ f(G) \ge \Delta \)，并且 \( \chi'_ f(G) \) 可以通过求解上述LP得到。 实际求解的LP形式 ：为了便于求解，我们固定颜色数 \( K \) 为一个足够大的数（比如 \( K = |E| \) 或 \( 2\Delta \)），并直接求解以下线性规划，然后通过舍入得到整数解。但更常见的近似算法方法是：先求解上述关于t的LP得到最优值 \( t^* \)，然后通过某种舍入过程构造一个整数边染色，使用的颜色数最多为 \( \lceil t^* \rceil + 1 \) 或 \( \lceil t^* \rceil + O(1) \)。然而，这需要复杂的随机舍入和修正步骤。 为简化讲解 ，我们采用另一种常见的整数规划松弛，然后进行随机舍入，并分析近似比。具体模型如下： 设颜色集合为 \( \{1, 2, ..., K\} \)，其中 \( K \) 是某个足够大的数（比如 \( 2\Delta \)）。我们引入0-1变量： \( y_ c = 1 \) 如果颜色c被使用，否则为0。 \( x_ {e,c} = 1 \) 如果边e被染成颜色c，否则为0。 整数规划（IP）为： \[ \begin{aligned} \text{minimize} \quad & \sum_ {c=1}^{K} y_ c \\ \text{subject to} \quad & \sum_ {c=1}^{K} x_ {e,c} = 1, \quad \forall e \in E \\ & \sum_ {e \in \delta(v)} x_ {e,c} \le 1, \quad \forall v \in V, \forall c \\ & x_ {e,c} \le y_ c, \quad \forall e \in E, \forall c \\ & x_ {e,c} \in \{0,1\}, \quad y_ c \in \{0,1\}. \end{aligned} \] 约束解释： 每条边必须被分配恰好一种颜色。 在每个顶点v上，每种颜色至多被分配给一条关联边（相邻边不同色）。 如果颜色c没有被使用（\( y_ c=0 \)），则任何边都不能被染成颜色c。 线性规划松弛 ：将 \( x_ {e,c} \) 和 \( y_ c \) 松弛到 [ 0,1] 区间，得到LP。设LP的最优值为 \( OPT_ {LP} \)。显然 \( OPT_ {LP} \le \chi'(G) \)（整数规划最优值）。 3. 求解线性规划松弛 我们可以用任何线性规划求解器（例如单纯形法、内点法）求解上述LP。求解后得到分数解 \( x_ {e,c}^ , y_ c^ \)。注意到，由于约束 \( \sum_ {c} x_ {e,c} = 1 \)，且每个顶点-颜色对的和 ≤ 1，我们可以推导出 \( OPT_ {LP} \ge \Delta \)，因为每个顶点的度数至少为 \( \Delta \) 的顶点，其关联边的颜色分配总和至少为 \( \Delta \)，而每种颜色在每个顶点上贡献至多1，所以至少需要 \( \Delta \) 种颜色（分数意义上）。实际上，可以证明 \( OPT_ {LP} = \chi'_ f(G) \)，且满足 \( \Delta \le \chi'_ f(G) \le \chi'(G) \le \Delta + 1 \)。 算法步骤1 ：求解LP松弛，得到最优解 \( (x^ , y^ ) \)。设 \( t^* = \sum_ c y_ c^* \)（分数颜色数）。事实上，由于 \( y_ c^* \) 是分数，这个和可能不是整数，但可以证明 \( t^* = \chi'_ f(G) \)。 4. 随机舍入与冲突处理 现在我们有一个分数解 \( x_ {e,c}^* \)。我们需要将其舍入为一个整数解（即一个合法的边染色）。一个自然的想法是 随机舍入 ：对每条边e，我们根据分布 \( \{ x_ {e,c}^* \} \) 独立地随机选择一种颜色c。但这样会导致冲突：一个顶点上可能有多条边被赋予了相同颜色，违反相邻边不同色的约束。 如何解决冲突 ？我们可以采用以下步骤： 随机舍入 ：对每条边e，独立地以概率 \( x_ {e,c}^* \) 将其“临时”分配给颜色c。注意，由于 \( \sum_ c x_ {e,c}^* = 1 \)，这是一个概率分布。 冲突检测 ：对于每个顶点v和每种颜色c，检查v的关联边中有多少条被分配了颜色c。如果超过1条，则发生冲突。 冲突解决 ：我们需要重新分配冲突边的颜色，使得每个顶点-颜色对最多只有一条边。一种方法是：对于每个顶点v，如果有多条边被赋予颜色c，我们只保留其中一条（随机选择），其他边标记为“未着色”。然后，对未着色的边，重新进行染色，但这个过程可能复杂，且可能导致颜色数增加。 更系统的舍入方法 ：我们可以将分数解 \( x_ {e,c}^* \) 视为一个“概率分布”，然后尝试为每条边分配颜色，使得每个顶点上每种颜色至多出现一次。这实际上是一个 匹配问题 ：对于每种颜色c，考虑子图 \( H_ c \)，其中顶点集为V，边集为被赋予颜色c的边（在舍入后）。我们希望 \( H_ c \) 是一个匹配（即每个顶点度数 ≤ 1）。但随机舍入后， \( H_ c \) 可能不是匹配。 标准技巧 ：利用 劳瓦尔局部引理（Lovász Local Lemma, LLL） 或 条件概率法 来构造一个无冲突的舍入。但这里我们描述一个更简单的 迭代随机舍入 方法，它基于以下观察： 分数解 \( x^* \) 满足每个顶点v上，所有边和所有颜色的总和为 \( \sum_ {e \in \delta(v)} \sum_ c x_ {e,c}^* = |\delta(v)| \)。同时，对每个顶点v和每种颜色c，有 \( \sum_ {e \in \delta(v)} x_ {e,c}^* \le 1 \)。这意味着向量 \( (x_ {e,c}^* ) \) 可以看作是“边-颜色对”上的一个 分数匹配 ，其中每个顶点-颜色对是一个“资源”，每个边是一个“任务”。 我们可以将问题转化为 超图匹配 的舍入。已知有结果：上述线性规划的分数解可以通过舍入得到一个整数解，使用的颜色数最多为 \( \lceil t^* \rceil + 1 \)。具体算法如下： 设 \( t = \lceil t^* \rceil \)。 我们准备 \( t+1 \) 种颜色。目标是用这 \( t+1 \) 种颜色构造一个合法的边染色。 从分数解 \( x^* \) 出发，我们为每条边e独立地随机选择一种颜色c，但选择概率为 \( x_ {e,c}^* / t^* \) 的调整？这里需要小心，因为 \( \sum_ c x_ {e,c}^* = 1 \)，而 \( t^* \ge 1 \)。如果我们简单地以概率 \( x_ {e,c}^* \) 选择颜色c，那么每种颜色c被选中的概率为 \( y_ c^* \)，而 \( \sum_ c y_ c^* = t^* \)。但我们需要确保每条边只选一种颜色，且每个顶点上每种颜色至多出现一次。 实际上，有一个经典的舍入算法： 求解LP，得到 \( x^* \)。 对于每条边e，定义其颜色列表 \( L_ e = \{ c : x_ {e,c}^* > 0 \} \)。 对于每个顶点v，以及每种颜色c，定义“容量”为1。 这是一个 列表边染色 问题，其中每个边有一个颜色列表，每个顶点-颜色对有容量限制。 已知如果每个列表大小至少为 \( t+1 \)，且每个颜色在顶点v的关联边的列表中出现次数不超过某个界，则可以找到可行染色。在我们的LP解中，每个边e的列表大小期望至少为1，但可能需要扩展。 更实用的方法 ：由于边色数的近似算法有已知结果，我们可以直接利用以下事实：存在多项式时间算法，能够用 \( \Delta + 1 \) 种颜色边染色任何简单图。这已经是Vizing定理的构造性证明给出的算法。但如果我们想基于LP舍入得到一个近似比略大于1的算法，可以采用以下步骤： 求解LP得到 \( t^* \)。 令 \( k = \lceil t^* \rceil + 1 \)。由于 \( t^* \ge \Delta \)，我们有 \( k \le \Delta + 2 \)（因为 \( t^* \le \Delta + 1 \)，所以 \( k \le \Delta + 2 \)）。 然后，利用 多项式时间算法 （如二分图边染色算法）为原图构造一个 \( k \) 种颜色的边染色。具体地，我们可以将原图转化为 线图 ，则边染色问题转化为线图的顶点染色问题。然后使用顶点染色的近似算法（如基于半定规划的舍入算法）对线图进行顶点染色，可以得到使用大约 \( 1.1 \chi \) 种颜色的染色，其中 \( \chi \) 是线图的色数（即原图的边色数）。但线图的顶点度数可能很大，导致近似比变差。 为了保持简单 ，我们给出一个基于LP舍入的简单随机算法思路，并分析其期望性能： 算法步骤 ： 求解LP，得到最优解 \( x_ {e,c}^* \) 和 \( t^* = \sum_ c y_ c^* \)。 令颜色数 \( k = \lceil t^* \rceil + 1 \)。 构造一个随机边染色如下： 初始化所有边未染色。 对每种颜色 \( c = 1, 2, ..., k \)，执行以下操作： a. 根据分数解 \( x^* \)，以概率 \( x_ {e,c}^* \) 将边e加入颜色c的候选集合（独立地对每条边进行）。 b. 对于每个顶点v，如果有多条关联边在候选集合中，则只保留其中一条（随机选择），其余从候选集合中移除。 c. 将候选集合中的边正式染成颜色c，并标记为已染色。 对未染色的边，递归地重复此过程（用剩余的颜色）。 算法分析 ：可以证明，经过一轮（k种颜色）后，每条边以常数概率被染色。重复对数轮后，所有边都能被染色。最终使用的颜色数为 \( O(k \log n) \)，但这不是一个紧的界。 实际上，已知存在更精巧的舍入方法，可以得到使用 \( \lceil t^* \rceil + 1 \) 种颜色的边染色。这需要利用 整数分解定理 （因为分数边染色多面体是匹配多面体的张量积，其整数间隙为1）。但证明较复杂，超出了本示例的范围。 5. 示例演示 考虑一个简单图：三角形（3个顶点，3条边）。最大度数 \( \Delta = 2 \)。已知三角形是奇环，其边色数为3（即 \( \Delta+1 \)）。 建立LP ：设颜色数上界 \( K=3 \)。变量：\( x_ {e1,c}, x_ {e2,c}, x_ {e3,c} \) 对于三条边和3种颜色，以及 \( y_ 1, y_ 2, y_ 3 \)。 约束： 每条边颜色和=1。 每个顶点-颜色对：例如顶点v1关联边e1,e2，对颜色1：\( x_ {e1,1} + x_ {e2,1} \le 1 \)。 \( x_ {e,c} \le y_ c \)。 目标：最小化 \( y_ 1+y_ 2+y_ 3 \)。 求解LP（例如单纯形法），得到最优解：每条边均匀分配三种颜色，即 \( x_ {e,c}^* = 1/3 \) 对所有e,c，且 \( y_ c^* = 1/3 \)。目标值 \( OPT_ {LP} = 1 \)。这小于整数最优值3，说明松弛间隙很大。但注意，我们这里使用的K=3可能太小，导致LP松弛不紧。实际上，分数边色数 \( \chi' f \) 对于三角形是2（因为可以给每条边分配两种颜色各1/2），但我们这里建模中K=3，且约束 \( x {e,c} \le y_ c \) 导致 \( y_ c \) 必须 ≥ 每条边的颜色c的分数，所以 \( y_ c \) 至少为1/3，总和至少为1。若我们使用更一般的分数边染色LP（最小化t的那个），可以得到 \( t^* = 1.5 \)（因为每条边分给两种颜色各1/2，每个顶点上每种颜色总和为1）。这更接近真实分数色数。 舍入 ：从分数解出发，我们可以采用随机舍入。例如，对每条边，以1/2概率选颜色1，1/2概率选颜色2。但可能产生冲突（一个顶点有两条边同色）。我们可以重新分配冲突的边，最终可能需要3种颜色。实际上，三角形必须用3种颜色，所以舍入后得到3种颜色，而 \( t^ =1.5 \)，所以 \( \lceil t^ \rceil + 1 = 3 \)，这正是最优解。 6. 总结 边染色问题可以用线性规划松弛来建模，其分数最优值 \( \chi'_ f(G) \) 满足 \( \Delta \le \chi'_ f(G) \le \chi'(G) \le \Delta + 1 \)。 通过求解LP并舍入，可以构造一个使用最多 \( \lceil \chi'_ f(G) \rceil + 1 \) 种颜色的边染色，这意味着最多使用 \( \Delta + 2 \) 种颜色。但已知Vizing定理的构造性算法可以达到 \( \Delta + 1 \) 种颜色，所以LP舍入算法的主要理论意义在于提供了分数下界，并可以扩展到更复杂的约束（如列表边染色）。 这个示例展示了如何将组合优化问题建模为整数线性规划，通过线性规划松弛获得下界，并设计舍入算法得到近似解。