由于初始 $s_e = 1$，第一次增加时 ε 可能为 1。但如果某条边 e = (v, u) 的另一个端点 u 的 y_u 已大于 0，则 $s_e = 1 - y_u$，ε 会小于 1。

基于线性规划的图最小边覆盖问题的对偶上升算法求解示例 1. 问题描述 在组合优化中，图的“边覆盖”是图论中的一个经典问题。给定一个 无向图 G = (V, E)，其中 V 是顶点集合，E 是边集合。一个“边覆盖”定义为一个边子集 S ⊆ E，使得图 G 中的 每一个顶点 都至少与 S 中的一条边 关联 （即该顶点是 S 中某条边的端点）。我们的目标是找到这样一个边子集 S，并且希望 S 包含的 边数最少 。这就是“最小边覆盖”问题。 注意： 最小边覆盖与最小顶点覆盖、最大匹配等问题有密切联系。 如果图中有孤立顶点（没有边与之相连），则不存在边覆盖。 在二分图中，最小边覆盖问题可以在多项式时间内解决，但本示例讨论的算法是适用于一般无向图的，基于线性规划对偶理论的对偶上升算法。 这个问题可以形式化地写成一个整数线性规划： \[ \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} \] 其中： 决策变量 \(x_ e\) 表示边 e 是否被选入边覆盖 S（1 表示选中，0 表示不选）。 约束 \(\sum_ {e \in \delta(v)} x_ e \ge 1\) 表示对于每个顶点 v，至少有一条与 v 关联的边被选中（\(\delta(v)\) 表示与顶点 v 关联的边集）。 2. 线性规划松弛与对偶 整数规划是 NP-hard 的，所以我们先将其松弛为线性规划，以便利用对偶理论： \[ \begin{aligned} \text{(LP)} \quad \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 > 1\)，我们可以将其降到 1 而不违反约束，且目标值更小，所以最优解中 \(x_ e \le 1\) 自动满足）。 接下来，我们写出这个线性规划的对偶问题。为每个顶点约束引入对偶变量 \(y_ v \ge 0\)。根据线性规划对偶规则： \[ \begin{aligned} \text{(DP)} \quad \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} \] 解释：对偶问题中，每条边 e = (u, v) 对应一个约束，即该边两个端点的对偶变量之和不超过 1。这是一个“ 边打包 ”问题：我们希望给每个顶点分配一个非负权重 y_ v，使得每条边上的权重和不超过 1，并最大化所有顶点的权重和。 3. 对偶上升算法原理 互补松弛条件 是连接原问题和对偶问题最优解的关键： 原始互补松弛条件 ：对于每条边 e = (u, v)，如果 \(x_ e > 0\)，则对应的对偶约束必须紧，即 \(y_ u + y_ v = 1\)。 对偶互补松弛条件 ：对于每个顶点 v，如果 \(y_ v > 0\)，则对应的原始约束必须紧，即 \(\sum_ {e \in \delta(v)} x_ e = 1\)。 对偶上升算法的基本思想 ： 从对偶可行解（如全零）开始，逐步增加对偶变量的值，以增大对偶目标 \(\sum y_ v\)，同时始终保持对偶可行性（即 \(y_ u + y_ v \le 1\) 对所有边成立）。 在对偶变量上升过程中，利用互补松弛条件来指导构造原始可行解（即边覆盖）。 最终，当无法再增加任何对偶变量时，我们得到一个 最大对偶可行解 ，并根据互补松弛条件构造出一个 原始可行解 （即边覆盖）。如果我们构造的原始解恰好满足互补松弛条件，则它也是原始线性规划的最优解。但因为我们求解的是整数解，可能需要一些舍入或调整。 4. 算法详细步骤 下面是一个具体的 对偶上升算法 ，用于找到最小边覆盖的整数解： 输入 ：无向图 G = (V, E)，假设没有孤立顶点。 输出 ：一个边覆盖 S。 步骤 1：初始化 设置所有对偶变量 \(y_ v = 0\)。 设置边覆盖 S = ∅。 标记所有顶点为“未覆盖”。 对于每条边 e ∈ E，定义其“松弛量” \(s_ e = 1 - y_ u - y_ v\)。初始时，\(s_ e = 1\)。 步骤 2：迭代增加对偶变量 只要存在未覆盖的顶点，执行以下循环： a. 选择一个未覆盖的顶点 v。 b. 将 \(y_ v\) 增加 ε，其中 ε 是最大可能增量，使得不违反任何对偶约束。即： \[ \varepsilon = \min\{ s_ e \mid e = (v, u) \in E, \, u \text{ 是任意邻居顶点} \}. \] 由于初始 \(s_ e = 1\)，第一次增加时 ε 可能为 1。但如果某条边 e = (v, u) 的另一个端点 u 的 y_ u 已大于 0，则 \(s_ e = 1 - y_ u\)，ε 会小于 1。 c. 更新所有与 v 关联的边的松弛量：\(s_ e \leftarrow s_ e - \varepsilon\)。 d. 如果某条边 e = (v, u) 的松弛量 \(s_ e\) 变为 0，则称该边“紧”。此时，根据互补松弛条件，如果 \(x_ e > 0\)，则应有 \(y_ u + y_ v = 1\)。因此，我们可以考虑将这条边 e 加入候选集合。 步骤 3：构造边覆盖 在算法执行过程中，我们维护一个集合 T，包含所有“紧”的边（即满足 \(y_ u + y_ v = 1\) 的边）。 算法结束时（所有顶点都被覆盖？注意：对偶上升过程本身不保证所有顶点被覆盖，我们需要从 T 中选边构造覆盖）： a. 考虑集合 T。T 中的边构成了一个“边打包”的支撑结构。 b. 在 T 中寻找一个 极大匹配 M （即无法再添加边而不破坏匹配性质）。这可以通过贪心算法实现：按任意顺序考虑 T 中的边，如果一条边的两个端点都未被匹配，则将其加入 M。 c. 令边覆盖 S = M ∪ { 对于每个未被 M 覆盖的顶点 v，任选一条与 v 关联的边（可以是 T 中的，也可以是 E 中的）}。因为原图无孤立顶点，这样的边一定存在。 步骤 4：输出 S 5. 实例演示 考虑一个简单图：V = {1, 2, 3, 4}，E = {(1,2), (2,3), (3,4), (4,1), (2,4)}，即一个四边形加一条对角线。 初始化 ：y = (0,0,0,0)，所有顶点未覆盖，S = ∅。 迭代 1 ：选择未覆盖顶点 1。邻居边有 (1,2) 和 (1,4)，松弛量均为 1，所以 ε = 1。增加 y₁ 到 1。更新边 (1,2) 和 (1,4) 的松弛量：s_ {1,2}=0, s_ {1,4}=0。这两条边变为“紧”，加入 T。现在 T = {(1,2), (1,4)}。 迭代 2 ：选择未覆盖顶点 2（虽然与顶点 1 关联的边已紧，但顶点 2 本身可能未被覆盖）。检查与顶点 2 关联的边： (1,2) 已紧（s=0），(2,3) 松弛量=1，(2,4) 松弛量=1。因为 (1,2) 已紧，不能再通过增加 y₂ 来使 (1,2) 更紧，但增加 y₂ 会影响 (2,3) 和 (2,4)。为了保持对偶可行性，我们只能增加 y₂ 直到某条边变紧。计算 ε = min{ s_ {2,3}, s_ {2,4} } = min{1, 1} = 1。增加 y₂ 到 1。更新 s_ {2,3}=0, s_ {2,4}=0。将 (2,3) 和 (2,4) 加入 T。现在 T = {(1,2), (1,4), (2,3), (2,4)}。 迭代 3 ：此时顶点 3 和 4 尚未被考虑（但注意，顶点 3 和 4 可能已通过边与 y 值关联）。选择未覆盖顶点 3。与顶点 3 关联的边： (2,3) 已紧（s=0），(3,4) 松弛量=1。只能通过增加 y₃ 来调整 (3,4)。计算 ε = s_ {3,4} = 1。增加 y₃ 到 1。更新 s_ {3,4}=0。将 (3,4) 加入 T。现在 T 包含所有 5 条边？实际上 (1,2) 已重复，T = {(1,2), (1,4), (2,3), (2,4), (3,4)}。 此时，所有顶点 v 的 y_ v 都为 1，但每条边 e 的约束 y_ u + y_ v ≤ 1 被违反了吗？检查：对于边 (1,2)，y₁ + y₂ = 2 > 1，违反了约束！这说明我们的迭代过程有问题：在增加对偶变量时，必须同时考虑所有关联边的约束，当某条边的松弛量 s_ e 变为 0 时，就不能再增加其端点的 y 值了。 实际上，正确的对偶上升过程需要更谨慎地控制增量。让我们重新执行： 重新执行 ： 初始化：y = (0,0,0,0)，T = ∅。 选顶点 1：ε = min{1-0-0, 1-0-0} = 1。增加 y₁=1。边 (1,2) 和 (1,4) 变紧，T = {(1,2), (1,4)}。现在顶点 2 和 4 通过紧边与顶点 1 连接，但 y₂ 和 y₄ 仍为 0。 选顶点 2：与顶点 2 关联的边有 (1,2)（已紧，s=0），(2,3)（s=1），(2,4)（s=1）。由于 (1,2) 已紧，y₂ 的增加受限于 y₁ + y₂ ≤ 1，即 y₂ ≤ 1 - y₁ = 0。所以 ε = 0！因此顶点 2 的 y 值不能增加。同样，对于顶点 4，受限于边 (1,4)，y₄ 也不能增加。 此时，顶点 2 和 4 的 y 值仍为 0，但顶点 3 还未被考虑。选顶点 3：关联边 (2,3)（s=1），(3,4)（s=1）。由于 y₂=0，y₃ 可以增加到 1 而不违反任何约束？等一下，如果增加 y₃，需要考虑 (2,3) 和 (3,4)。计算 ε = min{1 - y₂ - y₃, 1 - y₃ - y₄} = min{1-0-0, 1-0-0} = 1。所以增加 y₃=1。边 (2,3) 和 (3,4) 变紧，加入 T。T = {(1,2), (1,4), (2,3), (3,4)}。 现在顶点 2 的关联边 (2,3) 已紧，所以 y₂ 仍不能增加（因为 y₂ ≤ 1 - y₃ = 0）。顶点 4 的关联边 (3,4) 已紧，所以 y₄ 也不能增加（y₄ ≤ 1 - y₃ = 0）。此时，所有顶点的状态：y₁=1, y₂=0, y₃=1, y₄=0。对偶目标值 = 2。 检查对偶可行性：对于每条边： (1,2): y₁+y₂=1 ≤ 1，紧。 (1,4): 1+0=1，紧。 (2,3): 0+1=1，紧。 (3,4): 1+0=1，紧。 (2,4): 0+0=0 ≤ 1，松。 所以对偶可行。 步骤 3 ：T = {(1,2), (1,4), (2,3), (3,4)}。在 T 中找极大匹配 M。贪心地： 选 (1,2) 加入 M，顶点 1 和 2 被覆盖。 下一条边 (1,4) 与 M 冲突（顶点 1 已匹配），跳过。 选 (2,3) 冲突（顶点 2 已匹配），跳过。 选 (3,4) 加入 M，顶点 3 和 4 被覆盖。 现在 M = {(1,2), (3,4)}。所有顶点都被匹配，所以 S = M 就是一个边覆盖，大小为 2。 验证：边集 {(1,2), (3,4)} 确实覆盖了所有顶点。事实上，这也是最小边覆盖，因为该图没有完美匹配但最大匹配大小为 2，最小边覆盖 = |V| - 最大匹配 = 4 - 2 = 2。这里我们通过算法得到了最优解。 6. 算法分析 对偶上升算法 在这里实际上模拟了寻找 最大匹配 的过程。对偶变量 y 可以视为顶点“价格”，紧边对应匹配边。最终构造的边覆盖基于最大匹配，并加上额外的边覆盖未匹配顶点。 在二分图中，这个算法等价于经典的“从最大匹配构造最小边覆盖”的方法。 算法的时间复杂度主要取决于对偶变量的调整和紧边的收集，但可以通过更高效的实现（如贪心匹配）达到 O(|E|) 时间。 这个算法得到的是整数解，且对于最小边覆盖问题，线性规划松弛的最优解一定是整数（因为约束矩阵是全单模的），所以对偶上升算法能得到精确最优解。 7. 总结 本示例介绍了如何利用 对偶上升算法 求解最小边覆盖问题。该算法通过对偶问题的变量逐步增加，并利用互补松弛条件，最终构造出原问题的最优解。关键步骤包括对偶变量的迭代增加、紧边的识别以及从紧边集合中构造边覆盖。该算法不仅提供了对最小边覆盖问题的高效求解方法，也展示了线性规划对偶理论在图优化问题中的强大应用。