基于线性规划的图边着色问题的多项式时间算法求解示例
我将为你讲解如何用线性规划方法解决图边着色问题，并给出多项式时间算法。
一、问题描述
图边着色问题：给定一个无向简单图 \(G = (V, E)\)，用尽可能少的颜色对图中的每条边进行着色，要求任意两条相邻的边（即共享一个公共顶点的两条边）必须着不同颜色。所需的最少颜色数称为图的边色数，记为 \(\chi'(G)\)。
这是一个经典的组合优化问题。对于一般图，确定边色数是NP难的，但我们可以用线性规划松弛来近似求解，并对某些特殊图（如二分图）设计多项式时间精确算法。
二、问题建模
1. 整数规划模型
设可用颜色集合为 \(C = \{1, 2, ..., k\}\)，其中 \(k\) 是一个足够大的数（例如 \(k = |E|\)）。
定义决策变量：
\[x_{e,c} = \begin{cases} 1, & \text{如果边 } e \text{ 着颜色 } c \\ 0, & \text{否则} \end{cases} \]
目标是最小化使用的颜色总数，但更常见的等价形式是：给定颜色数 \(k\)，判断是否能用 \(k\) 种颜色完成边着色。我们可以通过二分搜索最小的 \(k\) 来找到边色数。
对于固定的 \(k\)，约束条件为：
- 每条边必须且仅着一种颜色：
\[ \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 \in C \]
其中 \(\delta(v)\) 表示与顶点 \(v\) 相关联的边集合。
3. 整数约束：
\[ x_{e,c} \in \{0, 1\}, \quad \forall e \in E, c \in C \]
这是整数线性规划（ILP），直接求解是指数级的。
三、线性规划松弛
将整数约束松弛为线性约束：
\[0 \le x_{e,c} \le 1, \quad \forall e \in E, c \in C \]
其他约束不变。得到线性规划（LP）：
\[\begin{aligned} \text{LP:} \quad & \text{寻找可行解 } x_{e,c} \\ \text{s.t.} \quad & \sum_{c=1}^k x_{e,c} = 1, && \forall e \in E \\ & \sum_{e \in \delta(v)} x_{e,c} \le 1, && \forall v \in V, c \in C \\ & 0 \le x_{e,c} \le 1, && \forall e \in E, c \in C \end{aligned} \]
注意：这个LP的可行性意味着用 \(k\) 种颜色分数地着色是可能的。如果ILP不可行，LP可能仍然可行，所以LP最优值 \(k^*_{LP} \le \chi'(G)\)。
四、多项式时间算法设计
对于二分图，边着色问题可以在多项式时间内精确求解，并且LP松弛具有整数最优解。我们给出一个基于最大流的多项式时间算法。
1. 二分图边着色的特殊性质
Kőnig定理：对于二分图 \(G\)，其边色数等于最大度 \(\Delta(G)\)。即 \(\chi'(G) = \Delta\)。
因此，我们只需要用 \(\Delta\) 种颜色进行着色。算法思想是将边着色转化为一系列完美匹配的分解。
2. 逐步算法
输入：二分图 \(G = (U, V, E)\)，最大度 \(\Delta\)
输出：一个边着色方案，使用 \(\Delta\) 种颜色
步骤：
- 令当前颜色 \(c = 1\)。
- 构造辅助网络：
- 添加源点 \(s\) 和汇点 \(t\)。
- 从 \(s\) 到每个左部顶点 \(u \in U\) 连边，容量为 1。
- 从每个右部顶点 \(v \in V\) 到 \(t\) 连边，容量为 1。
- 对于原图中的每条边 \((u, v) \in E\)，如果尚未着色，则在网络中添加从 \(u\) 到 \(v\) 的边，容量为 1。
- 运行最大流算法（如Dinic或Edmonds-Karp）在辅助网络上求最大流。由于二分图的性质，最大流值等于当前未着色边构成子图的一个最大匹配的大小。
- 将最大流中流量为1的边（即匹配边）着色为颜色 \(c\)。
- 从原图中移除已着色的边。
- \(c \leftarrow c + 1\)。
- 如果还有未着色的边，返回步骤2。
正确性说明：
- 每次迭代找到的匹配是当前未着色边的一个匹配，因此匹配中的边在同一个顶点处不会冲突。
- 由于二分图的最大度是 \(\Delta\)，每次移除一个匹配后，剩余子图的最大度至少减少1，因此最多 \(\Delta\) 次迭代即可完成着色。
- 该算法的时间复杂度为 \(O(\Delta \cdot \text{MF}(|V|, |E|))\)，其中 \(\text{MF}\) 是最大流算法的时间复杂度。对于Dinic算法在单位容量图上为 \(O(\min\{|V|^{1/2}, |E|^{1/2}\} |E|)\)，因此总时间为多项式时间。
五、从分数解到整数解：一般图的舍入策略
对于非二分图，LP松弛可能没有整数最优解。但我们可以利用如下事实：
- 由Vizing定理，对于简单图，边色数满足 \(\Delta \le \chi'(G) \le \Delta + 1\)。
- 因此，LP松弛给出的下界 \(k^*_{LP}\) 至少为 \(\Delta\)。
近似算法思路：
- 求解LP松弛，得到分数解 \(x_{e,c}\)。
- 如果 \(k \ge \Delta + 1\)，则必有整数解（由Vizing定理），但构造性证明较复杂。
- 实践中，可以使用随机舍入或确定性舍入将分数解转为整数解，但需保证相邻边不同色。这通常需要复杂的组合方法。
六、举例说明
考虑一个简单二分图：\(G = (U, V, E)\)，其中 \(U = \{u1, u2\}\)，\(V = \{v1, v2\}\)，边为 \((u1, v1), (u1, v2), (u2, v1), (u2, v2)\)。最大度 \(\Delta = 2\)。
- 第一次迭代，构造网络流，找到一个完美匹配，例如 \((u1, v1)\) 和 \((u2, v2)\)，着颜色1。
- 移除这两条边后，剩下 \((u1, v2)\) 和 \((u2, v1)\)，构成另一个匹配，着颜色2。
- 完成边着色，使用2种颜色，等于 \(\Delta\)。
七、总结
- 图边着色问题可用整数规划建模，其线性规划松弛在二分图上具有整数最优解。
- 对于二分图，Kőnig定理保证了最优边色数为最大度，并可通过反复求最大匹配的多项式时间算法实现。
- 对于一般图，Vizing定理给出了边色数的紧界（\(\Delta\) 或 \(\Delta+1\)），但找到最小着色的多项式时间算法是困难的；LP松弛可提供下界，并可用于设计近似算法。
这个示例展示了如何将图着色问题转化为线性规划，并利用图论经典定理设计精确多项式算法。