基于线性规划的图最小边覆盖问题的整数规划建模、松弛与舍入算法求解示例
字数 8978 2025-12-08 12:19:55

基于线性规划的图最小边覆盖问题的整数规划建模、松弛与舍入算法求解示例

1. 问题描述

考虑一个无向图 G = (V, E)，其中 V 是顶点集合，|V| = n，E 是边集合，|E| = m。一个边覆盖（Edge Cover）是一个边的子集 C ⊆ E，使得图 G 中的每一个顶点都至少与 C 中的某一条边相关联（即每条边连接的两个顶点中至少有一个在 C 中）。我们的目标是找到一个包含边数最少的边覆盖，即最小边覆盖。

这是一个经典的组合优化问题，属于 NP-Hard 问题。我们可以将其建模为一个整数线性规划（Integer Linear Programming, ILP）问题，然后通过线性规划松弛和舍入算法来寻找近似最优解。

2. 整数规划建模

我们需要为每一条边 e ∈ E 定义一个决策变量 \(x_e\)：

  • \(x_e = 1\) 表示边 e 被选入边覆盖 C 中。
  • \(x_e = 0\) 表示边 e 没有被选中。

目标是最小化所选边的总数：\(\min \sum_{e \in E} x_e\)。

约束条件是什么？对于每一个顶点 v ∈ V，它必须被至少一条选中的边所“覆盖”。这意味着，与顶点 v 相关联的所有边中，至少有一条被选中。用数学语言描述，设 \(\delta(v)\) 表示与顶点 v 相关联的边集合（在无向图中，就是所有以 v 为一个端点的边）。那么约束为：对于每一个顶点 v ∈ V，有

\[\sum_{e \in \delta(v)} x_e \ge 1. \]

最后，\(x_e \in \{0, 1\}\)。因此，完整的整数规划模型为：

\[\begin{aligned} \min \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & \sum_{e \in \delta(v)} x_e \ge 1, \quad \forall v \in V, \\ & x_e \in \{0, 1\}, \quad \forall e \in E. \end{aligned} \]

我们称这个模型为 (IP)。

3. 线性规划松弛与对偶

问题 (IP) 是整数规划，直接求解困难。线性规划松弛（Linear Programming Relaxation, LP Relaxation）是一种常用技巧：我们将变量的整数约束 \(x_e \in \{0, 1\}\) 松弛为连续约束 \(0 \le x_e \le 1\)。因为原来约束是 \(x_e \in \{0, 1\}\)，其凸包是 [0, 1] 区间，并且新增的约束 \(x_e \le 1\) 是冗余的（为什么？因为原约束中已有 \(\sum_{e \in \delta(v)} x_e \ge 1\)，并且每个变量非负，如果某个 \(x_e > 1\) 并不会帮助更好地满足覆盖约束，反而增加目标值，所以最优解中不会出现大于1的值。但在标准LP松弛中，我们显式加上 \(x_e \le 1\) 是安全的，也可以不加，解自动满足。通常我们只松弛为 \(x_e \ge 0\)，因为约束已隐含了上界）。

因此，松弛后的线性规划（我们称为 (LP)）为：

\[\begin{aligned} \min \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & \sum_{e \in \delta(v)} x_e \ge 1, \quad \forall v \in V, \\ & x_e \ge 0, \quad \forall e \in E. \end{aligned} \]

注意，这里我们移除了 \(x_e \le 1\) 的约束，因为如前所述，在最小化目标下，最优解会自动满足 \(x_e \le 1\)。我们可以验证：假设某个顶点 v 只有一条关联边 e，则约束要求 \(x_e \ge 1\)。如果 v 有两条关联边 e, f，约束为 \(x_e + x_f \ge 1\)，最优解可能会让 \(x_e = 0.5, x_f = 0.5\)，都小于等于1。如果某个 \(x_e > 1\)，我们可以将其降至1而不违反任何约束（因为与 e 关联的两个顶点的约束中，其他边贡献非负，\(x_e\) 减少到1仍然能满足 ≥1），并且目标值降低。所以，确实在最优解中， \(0 \le x_e \le 1\) 自动成立。

现在我们写出 (LP) 的对偶问题 (Dual)。为每个顶点约束引入对偶变量 \(y_v \ge 0\)。根据线性规划对偶规则（原始最小化，约束为 ≥，对应对偶变量 ≥0；原始变量 \(x_e \ge 0\)，对应对偶约束为 ≤），得到对偶问题：

\[\begin{aligned} \max \quad & \sum_{v \in V} y_v \\ \text{s.t.} \quad & y_u + y_v \le 1, \quad \forall e = (u, v) \in E, \\ & y_v \ge 0, \quad \forall v \in V. \end{aligned} \]

解释：原始问题中每个变量 \(x_e\) 出现在两个顶点约束中（边 e 的两个端点 u 和 v），所以在对偶中，对每个边 e 有一个约束： \(y_u + y_v \le 1\)。

4. 线性规划松弛的最优解性质

我们先不直接求解 (LP)，而是分析其最优解的结构性质，这对于设计舍入算法很重要。

定理：(LP) 存在一个最优解 \(x^*\)，其中所有分量 \(x_e^*\) 要么是 0，要么是 1/2，要么是 1。更进一步，可以证明存在一个最优解是“半整数的”。

简要思路：由于目标函数和约束都是整齐的系数，并且约束矩阵是全单模矩阵吗？不，边覆盖问题的约束矩阵不是全单模的（因为最小边覆盖的整数规划不总是有整数最优解，例如三角形图的最优分数解可能是所有边赋值为1/2，目标1.5，而整数最优解是2，所以LP松弛有分数最优解）。但我们可以通过考虑基解的性质来论证：在最优基解中，基本变量的值由方程 \(Ax = b\) 确定，其中 b 是全1向量，A 的每一行对应一个顶点，每一列对应一条边，列向量中两个位置为1（边的两个端点）。这样的系统可以导出，基本变量的解是 0, 1/2, 或 1。这是一个已知结论。我们接受这个性质即可。

5. 舍入算法设计

假设我们已经得到了 (LP) 的一个最优解 \(x^*\)，其中 \(x_e^* \in \{0, \frac{1}{2}, 1\}\)。我们设计舍入算法，从 \(x^*\) 构造一个可行的整数解（即一个边覆盖）。

算法步骤如下：

  1. 求解线性规划 (LP)，得到最优解 \(x^*\)。
  2. 初始化：令整数解 \(\hat{x}_e = 0\) 对所有边 e。
  3. 舍入规则：
    • 对于满足 \(x_e^* = 1\) 的边 e，直接选取：令 \(\hat{x}_e = 1\)。
    • 对于满足 \(x_e^* = 1/2\) 的边，我们处理由这些边（即分数值为1/2的边）构成的子图。这个子图中每个顶点的度数是多少？考虑一个顶点 v，在原始解 \(x^*\) 中，有 \(\sum_{e \in \delta(v)} x_e^* = 1\)。如果有一条关联边 e 满足 \(x_e^* = 1\)，那么这个顶点的覆盖约束已经由该边满足，并且这个顶点的其他关联边在 \(x^*\) 中只能是0（因为如果还有另一条边分数为正，再加上1就会超过1，而对偶约束 \(y_u + y_v \le 1\) 在最优解中对于 \(x_e^* = 1\) 的边是紧的，但这里我们不深究）。关键是，对于那些在 \(x^*\) 中没有关联边为1的顶点，其所有关联边的 \(x^*\) 值之和为1，并且因为每个 \(x_e^*\) 是0或1/2，所以这样的顶点必须有恰好两条关联边的值为 1/2。因此，由值为 1/2 的边诱导的子图，其每个连通分量都是一个简单环或一条路径，并且环上每个顶点恰有两条关联边（在分量内），路径端点也恰有一条关联边（在分量内）。而且，这些分量中所有边的 \(x^*\) 值都是 1/2。
  4. 处理分数边：对于每个由值为 1/2 的边构成的连通分量（每个分量是一个环或路径）：
    • 如果分量是一个环（有偶数条边，因为每个顶点度数为2），我们可以交替选取环上的边。具体来说，对环的边进行二着色（因为是偶环，可以二染色），然后选取其中一种颜色的所有边。这样，环上每个顶点都恰好与一条被选中的边相关联（因为每个顶点连接两条边，且颜色不同）。
    • 如果分量是一条路径，我们也可以类似处理：对路径的边交替染色（从一端开始），然后选取其中一种颜色的所有边。这样，路径内部的每个顶点（度数2）会与一条被选中的边相关联。但路径的两个端点呢？端点只与一条边相关联（在分量内）。如果我们选择的颜色使得某个端点关联的边没有被选中，那么这个端点将不被这个分量中的任何边覆盖。但是，这个端点可能在原图中有其他值为1的边覆盖它吗？注意，我们之前分析：如果一个顶点在 \(x^*\) 中没有关联边为1，那么它的所有关联边在 \(x^*\) 中要么是0要么是1/2，并且和为1。如果它是某个路径的端点，那么它在分量内只有一条值为1/2的边。因为和为1，所以它必须还有另一条值为1/2的边？不，如果它是路径端点，在分量内只有一条边，值为1/2，那么为了满足和为1，它必须在分量外还有另一条值为1/2的边。但这样它的度数在分数边子图中至少是2（一条在路径内，另一条在别处），这违反了“由值为1/2的边构成的子图”的性质：在这样一个子图中，每个顶点的度数要么是1（路径端点），要么是2（环上点或路径内点）。如果端点在子图中度数为1，那么 \(\sum_{e \in \delta(v)} x_e^*\) 中，这条边贡献1/2，其他边贡献0，总和为1/2，不等于1，矛盾。所以，在最优解 \(x^*\) 中，值为1/2的边构成的子图中不可能存在度数为1的顶点！因为每个顶点必须满足覆盖约束等于1，而如果它只有一条值为1/2的关联边，总和仅为1/2，不满足约束。因此，这个子图中每个顶点的度数必须是偶数（0, 2, 4, ...），但值为1/2的边意味着这个顶点至少有一条这样的边。实际上，从约束 \(\sum_{e \in \delta(v)} x_e^* = 1\) 和 \(x_e^* \in \{0, 1/2, 1\}\) 可推出：如果顶点 v 没有值为1的边，那么它有偶数条值为1/2的边（因为每条边贡献1/2，要凑成整数1，必须有2条）。所以，值为1/2的边构成的子图中，每个顶点度数都是2（可能有多个连通分量，每个分量是若干个顶点不相交的环）。因此，实际上不会出现路径，所有分量都是环。
  5. 算法简化：因此，步骤变为：对每个由值为1/2的边构成的环，我们交替选取环上的边（即选取一个完美匹配）。这样，环上每个顶点都恰好被一条选中的边覆盖。
  6. 构造最终解：所有选取的边（包括原来 \(x_e^* = 1\) 的边和从环中选出的边）的集合 C 就是我们的边覆盖。

6. 算法近似比分析

我们的算法得到的整数解 \(\hat{x}\) 是可行的边覆盖吗？

  • 对于有值为1的边关联的顶点，显然被覆盖。
  • 对于只有值为1/2的边的顶点，它们都在某个环中，我们选择了环的一个完美匹配，环上每个顶点恰好与一条被选中的边关联，所以也被覆盖。

因此，C 是一个可行的边覆盖。

现在分析近似比，即算法得到的边覆盖大小与最优整数解（最小边覆盖）的比值上界。

设：

  • \(OPT_{IP}\) ：原整数规划 (IP) 的最优值（最小边覆盖的边数）。
  • \(OPT_{LP}\) ：线性规划 (LP) 的最优值（分数最优解的目标值）。
  • \(ALG\) ：我们算法得到的边覆盖的边数。

由于 (LP) 是 (IP) 的松弛，有 \(OPT_{LP} \le OPT_{IP}\)。

算法中，我们对每条值为1的边都选取（贡献1），对每个由值为1/2的边构成的环，如果环有 k 条边，我们选取其中的 k/2 条边（因为交替选一边）。

设：

  • \(E_1 = \{ e \in E : x_e^* = 1 \}\)，其边数为 \(|E_1|\)。
  • \(E_{1/2} = \{ e \in E : x_e^* = 1/2 \}\)，其边数为 \(|E_{1/2}|\)。

则 LP 最优值为：

\[OPT_{LP} = \sum_{e} x_e^* = 1 \cdot |E_1| + \frac{1}{2} \cdot |E_{1/2}|. \]

我们的算法选取的边数为：

\[ALG = |E_1| + \frac{1}{2} |E_{1/2}|. \]

（因为每个环的边数 k 是偶数，我们选取一半，所以总选取数为 \(|E_1| + \frac{1}{2}|E_{1/2}|\)）。

因此，我们有 \(ALG = OPT_{LP}\)。

所以，\(ALG = OPT_{LP} \le OPT_{IP}\)。

这意味着我们的算法得到的解的目标值等于 LP 松弛的最优值，而 LP 最优值是整数最优值的一个下界，所以 \(ALG\) 是整数最优值的一个下界？等等，这不对。因为 \(ALG\) 是一个可行整数解，其值应该大于等于最优整数解，即 \(ALG \ge OPT_{IP}\)。但我们推导出 \(ALG = OPT_{LP} \le OPT_{IP}\)，这产生了矛盾，除非等号成立。

矛盾出在哪里？错误在于：\(ALG\) 并不总是等于 \(|E_1| + \frac{1}{2}|E_{1/2}|\)。因为我们从环中选取边时，每个环我们选取了恰好一半的边，所以对于 \(E_{1/2}\) 中的边，我们确实选取了恰好一半。所以 \(ALG = |E_1| + \frac{1}{2}|E_{1/2}|\) 是正确的。那么矛盾如何解释？

实际上，最小边覆盖问题有一个著名的定理：在任意图中，最小边覆盖的大小等于顶点数减去最大匹配的大小（Gallai 定理）。并且，其整数规划 (IP) 的线性规划松弛 (LP) 是整数规划吗？不，如前所述，三角形图是一个反例：三角形图有三个顶点三条边，分数最优解是每条边赋值1/2，目标1.5，而整数最优解是2（任意两条边构成边覆盖）。所以 (LP) 的最优值可以是分数。但我们的舍入算法得到的整数解大小恰好等于这个分数最优值。这意味着对于三角形图，我们的算法能找到一个大小为1.5的边覆盖？但边覆盖的大小必须是整数。1.5不可能。这揭示了我们证明中的漏洞。

漏洞在于：我们假设了 LP 最优解 \(x^*\) 中，所有分量要么是0, 1/2, 1。但这并不保证 \(|E_{1/2}|\) 是偶数。在三角形例子中，三条边的值都是1/2，\(|E_{1/2}| = 3\)，是奇数。那么我们的舍入算法在“处理分数边”步骤中，由值为1/2的边构成的子图是三角形本身，它是一个环吗？三角形是一个环，但边数是3，是奇数。奇数条边的环无法进行“交替选取”使得每个顶点恰好覆盖一次。如果我们尝试交替选取，比如选取两条边，那么有两个顶点被覆盖两次，一个顶点没有被覆盖（如果选两条有公共顶点的边，那个公共顶点覆盖两次，另一个顶点没覆盖；如果选两条没有公共顶点的边，在三角形中不存在这样的两条边）。所以，我们的算法在三角形图上会失败，无法产生可行的边覆盖。

那么，我们之前关于“值为1/2的边构成的子图中每个顶点度数为2”的推导是否正确？在三角形图中，每个顶点有两条关联边，每条边值1/2，所以 \(\sum_{e \in \delta(v)} x_e^* = 1/2 + 1/2 = 1\)，满足约束。每个顶点在分数边子图中度数为2，没错。但三角形环的边数是3，是奇数。所以，确实存在奇数边的环。在这种情况下，我们不能简单地交替选取边来得到一个完美匹配，因为奇数环没有完美匹配。

修正算法：对于由值为1/2的边构成的每个连通分量（现在知道它可能是一个环，可能是更一般的结构，但可以证明它实际上是一个顶点度数均为偶数的子图，因此是欧拉图，可以分解为若干环，但可能边共享）。更简单的处理方法是：对于这样的分量，我们直接选取该分量中的所有边。但这样，目标值就增加了：原来分量中每条边贡献1/2，总贡献是 \((1/2) * |E(C)|\)，如果我们全取，贡献变为 \(|E(C)|\)，是原来的2倍。

所以，修正后的舍入规则：

  • 对于 \(x_e^* = 1\) 的边，直接选取。
  • 对于 \(x_e^* = 1/2\) 的边，考虑它们构成的子图 H。由于每个顶点在 H 中的度数为偶数（至少为2），H 可以分解为若干边不相交的环（欧拉子图）。对于 H 中的每个连通分量，我们选取该分量中的所有边。这样，这个分量中的每个顶点都被至少一条选中的边覆盖（实际上被覆盖了多次，但至少一次）。

修正后的近似比：设 \(E_{1/2}\) 中的边被全部选取，所以

\[ALG = |E_1| + |E_{1/2}|. \]

而

\[OPT_{LP} = |E_1| + \frac{1}{2} |E_{1/2}|. \]

因此，

\[ALG = |E_1| + |E_{1/2}| = (|E_1| + \frac{1}{2}|E_{1/2}|) + \frac{1}{2}|E_{1/2}| = OPT_{LP} + \frac{1}{2}|E_{1/2}|. \]

我们需要将 ALG 与 \(OPT_{IP}\) 比较。由于 \(OPT_{LP} \le OPT_{IP}\)，所以

\[ALG \le OPT_{LP} + \frac{1}{2}|E_{1/2}|. \]

但 \(|E_{1/2}|\) 可能很大。我们需要另一个关系。注意到，在任意可行解中，每个被选取的边覆盖两个顶点。但我们可以用最大匹配来 bound。实际上，有一个更紧的界。

已知结论：对于最小边覆盖问题，上述线性规划松弛 (LP) 的整数间隙（integrality gap）为 3/2。即，存在图使得 \(OPT_{IP} / OPT_{LP} = 3/2\)。我们的修正算法可以达到 2-近似，因为：

\[ALG = |E_1| + |E_{1/2}| \le 2(|E_1| + \frac{1}{2}|E_{1/2}|) = 2 \cdot OPT_{LP} \le 2 \cdot OPT_{IP}. \]

因为 \(|E_1| \ge 0\)，所以 \(|E_1| + |E_{1/2}| \le 2|E_1| + |E_{1/2}| = 2(|E_1| + \frac{1}{2}|E_{1/2}|)\)。确实，ALG ≤ 2 OPT_{LP} ≤ 2 OPT_{IP}。

事实上，我们可以设计一个更聪明的舍入得到 3/2-近似算法，但比较复杂。这里我们展示的简单舍入（取所有分数边）给出了一个 2-近似算法。因为 ALG ≤ 2 OPT_{LP} ≤ 2 OPT_{IP}。

7. 算法总结

  1. 建模：将最小边覆盖问题建模为整数规划 (IP)。
  2. 松弛：将 (IP) 松弛为线性规划 (LP)。
  3. 求解LP：用线性规划求解器求解 (LP)，得到最优解 \(x^*\)。
  4. 舍入：
    a. 初始化边覆盖 C = ∅。
    b. 将所有满足 \(x_e^* = 1\) 的边 e 加入 C。
    c. 考虑由满足 \(x_e^* = 1/2\) 的边构成的子图 H。将 H 中的所有边加入 C。
  5. 输出：C 即为一个边覆盖，其大小最多是最小边覆盖大小的2倍。

8. 举例说明

考虑一个三角形图，顶点 {1,2,3}，边 e12, e23, e13。

  • (LP) 最优解：\(x_{12}^* = x_{23}^* = x_{13}^* = 1/2\)，最优值 1.5。
  • 算法执行：没有 \(x_e^* = 1\) 的边。子图 H 包含所有三条边。将所有三条边加入 C。
  • 得到的边覆盖 C = {e12, e23, e13}，大小 |C| = 3。
  • 实际最小边覆盖大小为2（任意两条边即可）。
  • 近似比：3/2 = 1.5 ≤ 2，满足2-近似。

9. 结束语

这个例子展示了如何对整数规划进行线性规划松弛，然后通过分析松弛解的结构性质（半整性），设计舍入规则将其转化为整数解，并分析近似保证。虽然本例的简单舍入只达到2-近似，但更精细的算法可以达到3/2-近似。整个流程体现了线性规划在组合优化近似算法中的核心作用。

基于线性规划的图最小边覆盖问题的整数规划建模、松弛与舍入算法求解示例 1. 问题描述 考虑一个无向图 G = (V, E)，其中 V 是顶点集合，|V| = n，E 是边集合，|E| = m。一个 边覆盖 （Edge Cover）是一个边的子集 C ⊆ E，使得图 G 中的每一个顶点都至少与 C 中的某一条边相关联（即每条边连接的两个顶点中至少有一个在 C 中）。我们的目标是找到一个包含边数最少的边覆盖，即 最小边覆盖 。 这是一个经典的组合优化问题，属于 NP-Hard 问题。我们可以将其建模为一个整数线性规划（Integer Linear Programming, ILP）问题，然后通过 线性规划松弛 和 舍入算法 来寻找近似最优解。 2. 整数规划建模 我们需要为每一条边 e ∈ E 定义一个决策变量 \( x_ e \)： \( x_ e = 1 \) 表示边 e 被选入边覆盖 C 中。 \( x_ e = 0 \) 表示边 e 没有被选中。 目标是最小化所选边的总数：\( \min \sum_ {e \in E} x_ e \)。 约束条件是什么？对于每一个顶点 v ∈ V，它必须被至少一条选中的边所“覆盖”。这意味着，与顶点 v 相关联的所有边中，至少有一条被选中。用数学语言描述，设 \( \delta(v) \) 表示与顶点 v 相关联的边集合（在无向图中，就是所有以 v 为一个端点的边）。那么约束为：对于每一个顶点 v ∈ V，有 \[ \sum_ {e \in \delta(v)} x_ e \ge 1. \] 最后，\( x_ e \in \{0, 1\} \)。因此，完整的整数规划模型为： \[ \begin{aligned} \min \quad & \sum_ {e \in E} x_ e \\ \text{s.t.} \quad & \sum_ {e \in \delta(v)} x_ e \ge 1, \quad \forall v \in V, \\ & x_ e \in \{0, 1\}, \quad \forall e \in E. \end{aligned} \] 我们称这个模型为 (IP) 。 3. 线性规划松弛与对偶 问题 (IP) 是整数规划，直接求解困难。线性规划松弛（Linear Programming Relaxation, LP Relaxation）是一种常用技巧：我们将变量的整数约束 \( x_ e \in \{0, 1\} \) 松弛为连续约束 \( 0 \le x_ e \le 1 \)。因为原来约束是 \( x_ e \in \{0, 1\} \)，其凸包是 [ 0, 1] 区间，并且新增的约束 \( x_ e \le 1 \) 是冗余的（为什么？因为原约束中已有 \( \sum_ {e \in \delta(v)} x_ e \ge 1 \)，并且每个变量非负，如果某个 \( x_ e > 1 \) 并不会帮助更好地满足覆盖约束，反而增加目标值，所以最优解中不会出现大于1的值。但在标准LP松弛中，我们显式加上 \( x_ e \le 1 \) 是安全的，也可以不加，解自动满足。通常我们只松弛为 \( x_ e \ge 0 \)，因为约束已隐含了上界）。 因此，松弛后的线性规划（我们称为 (LP)）为： \[ \begin{aligned} \min \quad & \sum_ {e \in E} x_ e \\ \text{s.t.} \quad & \sum_ {e \in \delta(v)} x_ e \ge 1, \quad \forall v \in V, \\ & x_ e \ge 0, \quad \forall e \in E. \end{aligned} \] 注意，这里我们移除了 \( x_ e \le 1 \) 的约束，因为如前所述，在最小化目标下，最优解会自动满足 \( x_ e \le 1 \)。我们可以验证：假设某个顶点 v 只有一条关联边 e，则约束要求 \( x_ e \ge 1 \)。如果 v 有两条关联边 e, f，约束为 \( x_ e + x_ f \ge 1 \)，最优解可能会让 \( x_ e = 0.5, x_ f = 0.5 \)，都小于等于1。如果某个 \( x_ e > 1 \)，我们可以将其降至1而不违反任何约束（因为与 e 关联的两个顶点的约束中，其他边贡献非负，\( x_ e \) 减少到1仍然能满足 ≥1），并且目标值降低。所以，确实在最优解中， \( 0 \le x_ e \le 1 \) 自动成立。 现在我们写出 (LP) 的 对偶问题 (Dual) 。为每个顶点约束引入对偶变量 \( y_ v \ge 0 \)。根据线性规划对偶规则（原始最小化，约束为 ≥，对应对偶变量 ≥0；原始变量 \( x_ e \ge 0 \)，对应对偶约束为 ≤），得到对偶问题： \[ \begin{aligned} \max \quad & \sum_ {v \in V} y_ v \\ \text{s.t.} \quad & y_ u + y_ v \le 1, \quad \forall e = (u, v) \in E, \\ & y_ v \ge 0, \quad \forall v \in V. \end{aligned} \] 解释：原始问题中每个变量 \( x_ e \) 出现在两个顶点约束中（边 e 的两个端点 u 和 v），所以在对偶中，对每个边 e 有一个约束： \( y_ u + y_ v \le 1 \)。 4. 线性规划松弛的最优解性质 我们先不直接求解 (LP)，而是分析其最优解的结构性质，这对于设计舍入算法很重要。 定理 ：(LP) 存在一个最优解 \( x^* \)，其中所有分量 \( x_ e^* \) 要么是 0，要么是 1/2，要么是 1。更进一步，可以证明存在一个最优解是“半整数的”。 简要思路 ：由于目标函数和约束都是整齐的系数，并且约束矩阵是全单模矩阵吗？不，边覆盖问题的约束矩阵不是全单模的（因为最小边覆盖的整数规划不总是有整数最优解，例如三角形图的最优分数解可能是所有边赋值为1/2，目标1.5，而整数最优解是2，所以LP松弛有分数最优解）。但我们可以通过考虑基解的性质来论证：在最优基解中，基本变量的值由方程 \( Ax = b \) 确定，其中 b 是全1向量，A 的每一行对应一个顶点，每一列对应一条边，列向量中两个位置为1（边的两个端点）。这样的系统可以导出，基本变量的解是 0, 1/2, 或 1。这是一个已知结论。我们接受这个性质即可。 5. 舍入算法设计 假设我们已经得到了 (LP) 的一个最优解 \( x^* \)，其中 \( x_ e^* \in \{0, \frac{1}{2}, 1\} \)。我们设计舍入算法，从 \( x^* \) 构造一个可行的整数解（即一个边覆盖）。 算法步骤如下： 求解线性规划 (LP) ，得到最优解 \( x^* \)。 初始化 ：令整数解 \( \hat{x}_ e = 0 \) 对所有边 e。 舍入规则 ： 对于满足 \( x_ e^* = 1 \) 的边 e，直接选取：令 \( \hat{x}_ e = 1 \)。 对于满足 \( x_ e^* = 1/2 \) 的边，我们处理由这些边（即分数值为1/2的边）构成的子图。这个子图中每个顶点的度数是多少？考虑一个顶点 v，在原始解 \( x^* \) 中，有 \( \sum_ {e \in \delta(v)} x_ e^* = 1 \)。如果有一条关联边 e 满足 \( x_ e^* = 1 \)，那么这个顶点的覆盖约束已经由该边满足，并且这个顶点的其他关联边在 \( x^* \) 中只能是0（因为如果还有另一条边分数为正，再加上1就会超过1，而对偶约束 \( y_ u + y_ v \le 1 \) 在最优解中对于 \( x_ e^* = 1 \) 的边是紧的，但这里我们不深究）。关键是，对于那些在 \( x^* \) 中没有关联边为1的顶点，其所有关联边的 \( x^* \) 值之和为1，并且因为每个 \( x_ e^* \) 是0或1/2，所以这样的顶点必须有 恰好两条 关联边的值为 1/2。因此，由值为 1/2 的边诱导的子图，其每个连通分量都是一个 简单环 或 一条路径 ，并且环上每个顶点恰有两条关联边（在分量内），路径端点也恰有一条关联边（在分量内）。而且，这些分量中所有边的 \( x^* \) 值都是 1/2。 处理分数边 ：对于每个由值为 1/2 的边构成的连通分量（每个分量是一个环或路径）： 如果分量是一个 环 （有偶数条边，因为每个顶点度数为2），我们可以 交替选取 环上的边。具体来说，对环的边进行二着色（因为是偶环，可以二染色），然后选取其中一种颜色的所有边。这样，环上每个顶点都恰好与一条被选中的边相关联（因为每个顶点连接两条边，且颜色不同）。 如果分量是一条 路径 ，我们也可以类似处理：对路径的边交替染色（从一端开始），然后选取其中一种颜色的所有边。这样，路径内部的每个顶点（度数2）会与一条被选中的边相关联。但路径的两个端点呢？端点只与一条边相关联（在分量内）。如果我们选择的颜色使得某个端点关联的边没有被选中，那么这个端点将不被这个分量中的任何边覆盖。但是，这个端点可能在原图中有其他值为1的边覆盖它吗？注意，我们之前分析：如果一个顶点在 \( x^* \) 中没有关联边为1，那么它的所有关联边在 \( x^* \) 中要么是0要么是1/2，并且和为1。如果它是某个路径的端点，那么它在分量内只有一条值为1/2的边。因为和为1，所以它必须还有另一条值为1/2的边？不，如果它是路径端点，在分量内只有一条边，值为1/2，那么为了满足和为1，它必须在分量外还有另一条值为1/2的边。但这样它的度数在分数边子图中至少是2（一条在路径内，另一条在别处），这违反了“由值为1/2的边构成的子图”的性质：在这样一个子图中，每个顶点的度数要么是1（路径端点），要么是2（环上点或路径内点）。如果端点在子图中度数为1，那么 \( \sum_ {e \in \delta(v)} x_ e^* \) 中，这条边贡献1/2，其他边贡献0，总和为1/2，不等于1，矛盾。所以，在最优解 \( x^* \) 中，值为1/2的边构成的子图中不可能存在度数为1的顶点！因为每个顶点必须满足覆盖约束等于1，而如果它只有一条值为1/2的关联边，总和仅为1/2，不满足约束。因此，这个子图中每个顶点的度数必须是偶数（0, 2, 4, ...），但值为1/2的边意味着这个顶点至少有一条这样的边。实际上，从约束 \( \sum_ {e \in \delta(v)} x_ e^* = 1 \) 和 \( x_ e^* \in \{0, 1/2, 1\} \) 可推出：如果顶点 v 没有值为1的边，那么它有偶数条值为1/2的边（因为每条边贡献1/2，要凑成整数1，必须有2条）。所以，值为1/2的边构成的子图中，每个顶点度数都是2（可能有多个连通分量，每个分量是若干个顶点不相交的环）。因此，实际上不会出现路径，所有分量都是 环 。 算法简化 ：因此，步骤变为：对每个由值为1/2的边构成的环，我们交替选取环上的边（即选取一个完美匹配）。这样，环上每个顶点都恰好被一条选中的边覆盖。 构造最终解 ：所有选取的边（包括原来 \( x_ e^* = 1 \) 的边和从环中选出的边）的集合 C 就是我们的边覆盖。 6. 算法近似比分析 我们的算法得到的整数解 \( \hat{x} \) 是可行的边覆盖吗？ 对于有值为1的边关联的顶点，显然被覆盖。 对于只有值为1/2的边的顶点，它们都在某个环中，我们选择了环的一个完美匹配，环上每个顶点恰好与一条被选中的边关联，所以也被覆盖。 因此，C 是一个可行的边覆盖。 现在分析近似比，即算法得到的边覆盖大小与最优整数解（最小边覆盖）的比值上界。 设： \( OPT_ {IP} \) ：原整数规划 (IP) 的最优值（最小边覆盖的边数）。 \( OPT_ {LP} \) ：线性规划 (LP) 的最优值（分数最优解的目标值）。 \( ALG \) ：我们算法得到的边覆盖的边数。 由于 (LP) 是 (IP) 的松弛，有 \( OPT_ {LP} \le OPT_ {IP} \)。 算法中，我们对每条值为1的边都选取（贡献1），对每个由值为1/2的边构成的环，如果环有 k 条边，我们选取其中的 k/2 条边（因为交替选一边）。 设： \( E_ 1 = \{ e \in E : x_ e^* = 1 \} \)，其边数为 \( |E_ 1| \)。 \( E_ {1/2} = \{ e \in E : x_ e^* = 1/2 \} \)，其边数为 \( |E_ {1/2}| \)。 则 LP 最优值为： \[ OPT_ {LP} = \sum_ {e} x_ e^* = 1 \cdot |E_ 1| + \frac{1}{2} \cdot |E_ {1/2}|. \] 我们的算法选取的边数为： \[ ALG = |E_ 1| + \frac{1}{2} |E_ {1/2}|. \] （因为每个环的边数 k 是偶数，我们选取一半，所以总选取数为 \( |E_ 1| + \frac{1}{2}|E_ {1/2}| \)）。 因此，我们有 \( ALG = OPT_ {LP} \)。 所以，\( ALG = OPT_ {LP} \le OPT_ {IP} \)。 这意味着我们的算法得到的解的目标值等于 LP 松弛的最优值，而 LP 最优值是整数最优值的一个下界，所以 \( ALG \) 是整数最优值的一个 下界 ？等等，这不对。因为 \( ALG \) 是一个可行整数解，其值应该大于等于最优整数解，即 \( ALG \ge OPT_ {IP} \)。但我们推导出 \( ALG = OPT_ {LP} \le OPT_ {IP} \)，这产生了矛盾，除非等号成立。 矛盾出在哪里？错误在于：\( ALG \) 并不总是等于 \( |E_ 1| + \frac{1}{2}|E_ {1/2}| \)。因为我们从环中选取边时，每个环我们选取了恰好一半的边，所以对于 \( E_ {1/2} \) 中的边，我们确实选取了恰好一半。所以 \( ALG = |E_ 1| + \frac{1}{2}|E_ {1/2}| \) 是正确的。那么矛盾如何解释？ 实际上， 最小边覆盖问题有一个著名的定理 ：在任意图中，最小边覆盖的大小等于顶点数减去最大匹配的大小（Gallai 定理）。并且，其整数规划 (IP) 的线性规划松弛 (LP) 是 整数规划 吗？不，如前所述，三角形图是一个反例：三角形图有三个顶点三条边，分数最优解是每条边赋值1/2，目标1.5，而整数最优解是2（任意两条边构成边覆盖）。所以 (LP) 的最优值可以是分数。但我们的舍入算法得到的整数解大小恰好等于这个分数最优值。这意味着对于三角形图，我们的算法能找到一个大小为1.5的边覆盖？但边覆盖的大小必须是整数。1.5不可能。这揭示了我们证明中的漏洞。 漏洞在于 ：我们假设了 LP 最优解 \( x^* \) 中，所有分量要么是0, 1/2, 1。但这并不保证 \( |E_ {1/2}| \) 是偶数。在三角形例子中，三条边的值都是1/2，\( |E_ {1/2}| = 3 \)，是奇数。那么我们的舍入算法在“处理分数边”步骤中，由值为1/2的边构成的子图是三角形本身，它是一个环吗？三角形是一个环，但边数是3，是奇数。奇数条边的环无法进行“交替选取”使得每个顶点恰好覆盖一次。如果我们尝试交替选取，比如选取两条边，那么有两个顶点被覆盖两次，一个顶点没有被覆盖（如果选两条有公共顶点的边，那个公共顶点覆盖两次，另一个顶点没覆盖；如果选两条没有公共顶点的边，在三角形中不存在这样的两条边）。所以，我们的算法在三角形图上会失败，无法产生可行的边覆盖。 那么，我们之前关于“值为1/2的边构成的子图中每个顶点度数为2”的推导是否正确？在三角形图中，每个顶点有两条关联边，每条边值1/2，所以 \( \sum_ {e \in \delta(v)} x_ e^* = 1/2 + 1/2 = 1 \)，满足约束。每个顶点在分数边子图中度数为2，没错。但三角形环的边数是3，是奇数。所以，确实存在奇数边的环。在这种情况下，我们不能简单地交替选取边来得到一个完美匹配，因为奇数环没有完美匹配。 修正算法 ：对于由值为1/2的边构成的 每个连通分量 （现在知道它可能是一个环，可能是更一般的结构，但可以证明它实际上是一个 顶点度数均为偶数的子图 ，因此是欧拉图，可以分解为若干环，但可能边共享）。更简单的处理方法是：对于这样的分量，我们直接 选取该分量中的所有边 。但这样，目标值就增加了：原来分量中每条边贡献1/2，总贡献是 \( (1/2) * |E(C)| \)，如果我们全取，贡献变为 \( |E(C)| \)，是原来的2倍。 所以，修正后的舍入规则： 对于 \( x_ e^* = 1 \) 的边，直接选取。 对于 \( x_ e^* = 1/2 \) 的边，考虑它们构成的子图 H。由于每个顶点在 H 中的度数为偶数（至少为2），H 可以分解为若干边不相交的环（欧拉子图）。对于 H 中的每个连通分量，我们 选取该分量中的所有边 。这样，这个分量中的每个顶点都被至少一条选中的边覆盖（实际上被覆盖了多次，但至少一次）。 修正后的近似比 ：设 \( E_ {1/2} \) 中的边被全部选取，所以 \[ ALG = |E_ 1| + |E_ {1/2}|. \] 而 \[ OPT_ {LP} = |E_ 1| + \frac{1}{2} |E_ {1/2}|. \] 因此， \[ ALG = |E_ 1| + |E_ {1/2}| = (|E_ 1| + \frac{1}{2}|E_ {1/2}|) + \frac{1}{2}|E_ {1/2}| = OPT_ {LP} + \frac{1}{2}|E_ {1/2}|. \] 我们需要将 ALG 与 \( OPT_ {IP} \) 比较。由于 \( OPT_ {LP} \le OPT_ {IP} \)，所以 \[ ALG \le OPT_ {LP} + \frac{1}{2}|E_ {1/2}|. \] 但 \( |E_ {1/2}| \) 可能很大。我们需要另一个关系。注意到，在任意可行解中，每个被选取的边覆盖两个顶点。但我们可以用最大匹配来 bound。实际上，有一个更紧的界。 已知结论 ：对于最小边覆盖问题，上述线性规划松弛 (LP) 的整数间隙（integrality gap）为 3/2。即，存在图使得 \( OPT_ {IP} / OPT_ {LP} = 3/2 \)。我们的修正算法可以达到 2-近似，因为： \[ ALG = |E_ 1| + |E_ {1/2}| \le 2(|E_ 1| + \frac{1}{2}|E_ {1/2}|) = 2 \cdot OPT_ {LP} \le 2 \cdot OPT_ {IP}. \] 因为 \( |E_ 1| \ge 0 \)，所以 \( |E_ 1| + |E_ {1/2}| \le 2|E_ 1| + |E_ {1/2}| = 2(|E_ 1| + \frac{1}{2}|E_ {1/2}|) \)。确实，ALG ≤ 2 OPT_ {LP} ≤ 2 OPT_ {IP}。 事实上，我们可以设计一个更聪明的舍入得到 3/2-近似算法，但比较复杂。这里我们展示的简单舍入（取所有分数边）给出了一个 2-近似算法。因为 ALG ≤ 2 OPT_ {LP} ≤ 2 OPT_ {IP}。 7. 算法总结 建模 ：将最小边覆盖问题建模为整数规划 (IP)。 松弛 ：将 (IP) 松弛为线性规划 (LP)。 求解LP ：用线性规划求解器求解 (LP)，得到最优解 \( x^* \)。 舍入 ： a. 初始化边覆盖 C = ∅。 b. 将所有满足 \( x_ e^* = 1 \) 的边 e 加入 C。 c. 考虑由满足 \( x_ e^* = 1/2 \) 的边构成的子图 H。将 H 中的所有边加入 C。 输出 ：C 即为一个边覆盖，其大小最多是最小边覆盖大小的2倍。 8. 举例说明 考虑一个三角形图，顶点 {1,2,3}，边 e12, e23, e13。 (LP) 最优解：\( x_ {12}^* = x_ {23}^* = x_ {13}^* = 1/2 \)，最优值 1.5。 算法执行：没有 \( x_ e^* = 1 \) 的边。子图 H 包含所有三条边。将所有三条边加入 C。 得到的边覆盖 C = {e12, e23, e13}，大小 |C| = 3。 实际最小边覆盖大小为2（任意两条边即可）。 近似比：3/2 = 1.5 ≤ 2，满足2-近似。 9. 结束语 这个例子展示了如何对整数规划进行线性规划松弛，然后通过分析松弛解的结构性质（半整性），设计舍入规则将其转化为整数解，并分析近似保证。虽然本例的简单舍入只达到2-近似，但更精细的算法可以达到3/2-近似。整个流程体现了线性规划在组合优化近似算法中的核心作用。