基于线性规划的图最大匹配问题的增广路算法求解示例
我将为您讲解一个经典的图论问题及其基于线性规划的算法解法。这个问题是关于如何在一个图中找到最大匹配，我将从问题描述开始，逐步深入到线性规划建模和增广路算法的具体求解过程。
1. 问题描述
最大匹配问题 是图论和组合优化中的一个核心问题。
- 图：我们考虑一个无向图 G = (V, E)，其中 V 是顶点集合，E 是连接顶点的边集合。
- 匹配：匹配 M 是边集合 E 的一个子集，其中任意两条边都没有公共顶点。也就是说，在匹配 M 中，每个顶点最多与一条边相关联。
- 最大匹配：一个图可能有许多不同的匹配。所谓“最大匹配”，是指该匹配包含的边数达到所有可能匹配中的最大值。注意，最大匹配不一定是唯一的。
目标：给定一个无向图 G，找到它的一个最大匹配。
示例：设想一个任务分配场景，图中的顶点代表工人和任务，如果某个工人能胜任某个任务，就在他们之间连一条边。最大匹配就对应着一种最大化完成任务数量的分配方案。
2. 线性规划建模
首先，我们将最大匹配问题表述为一个整数线性规划（ILP）问题。
- 决策变量：为每条边 e ∈ E 引入一个0-1变量 \(x_e\)。
- \(x_e = 1\) 表示边 e 被选入匹配 M。
- \(x_e = 0\) 表示边 e 未被选入。
- 目标函数：最大化匹配的边数，即 \(\max \sum_{e \in E} x_e\)。
- 约束条件：为了保证匹配的定义（每个顶点至多关联一条边），对于每个顶点 v ∈ V，与它相连的所有边 e ∈ δ(v)（δ(v) 表示与顶点 v 关联的边集）的变量之和不能超过1。即：\(\sum_{e \in δ(v)} x_e \le 1, \quad \forall v \in V\)。
- 整数约束：\(x_e \in \{0, 1\}, \quad \forall e \in E\)。
因此，最大匹配问题的整数规划模型为：
\[\begin{aligned} \max \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & \sum_{e \in δ(v)} x_e \le 1, \quad \forall v \in V \\ & x_e \in \{0, 1\}, \quad \forall e \in E \end{aligned} \]
3. 线性规划松弛与对偶
上述模型是整数规划，求解困难。一个关键的步骤是将其松弛为线性规划（LP），即去掉整数约束，改为 \(x_e \ge 0\)。由于约束矩阵是全单模矩阵（对于二分图，邻接矩阵是全单模的；对于一般图，此LP的最优解可能不是整数，但最大匹配的LP松弛有一些特殊性质），这个线性规划松弛的最优解可以帮助我们找到原问题的最优解。
松弛后的线性规划（原始问题P）及其对偶问题（D）如下：
(P) 原始问题（松弛后）:
\[\begin{aligned} \max \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & \sum_{e \in δ(v)} x_e \le 1, \quad \forall v \in V \\ & x_e \ge 0, \quad \forall e \in E \end{aligned} \]
(D) 对偶问题:
为每个顶点约束引入对偶变量 \(y_v \ge 0\)。
\[\begin{aligned} \min \quad & \sum_{v \in V} y_v \\ \text{s.t.} \quad & y_u + y_v \ge 1, \quad \forall e = (u, v) \in E \\ & y_v \ge 0, \quad \forall v \in V \end{aligned} \]
对偶问题可以理解为：给每个顶点 v 分配一个非负的“势能” \(y_v\)，使得对于每条边，其两个端点的势能之和不小于1，目标是使所有顶点的势能总和最小。
4. 增广路算法与互补松弛条件
求解最大匹配最著名的组合算法是增广路算法。其核心思想是：从一个空匹配开始，反复寻找“增广路径”来增加匹配的大小。
- 增广路径：在现有匹配 M 下，一条从非匹配顶点开始，交替经过非匹配边和匹配边，最终结束于另一个非匹配顶点的路径。这样的路径上，非匹配边比匹配边多一条。
- 增广操作：将增广路径上的所有边的“匹配状态”取反（即非匹配边变为匹配边，匹配边变为非匹配边）。操作后，匹配的边数恰好增加1。
关键洞察：增广路算法与线性规划的对偶理论密切相关。我们可以动态维护一组满足互补松弛条件的原始解（匹配 M 的指示向量 \(x\)）和对偶解（顶点势能 \(y\)）。
互补松弛条件：
- 原始互补松弛：如果一条边 e = (u, v) 是匹配边 (\(x_e = 1\))，则要求对应的对偶约束是紧的，即 \(y_u + y_v = 1\)。
- 对偶互补松弛：如果一个顶点 v 的对偶变量 \(y_v > 0\)，则要求对应的原始约束是紧的，即顶点 v 在匹配 M 中是饱和的（恰好关联一条匹配边）。
5. 算法步骤详解（基于线性规划的原始-对偶视角）
以下算法是增广路算法的一种实现，它显式地维护了对偶变量，并利用互补松弛条件来指导搜索。
步骤0：初始化
- 设当前匹配 M = ∅。
- 初始化对偶变量。一个简单且可行的初始化是：对于所有顶点 v，设 \(y_v = 0.5\)。这显然满足对偶约束 \(y_u + y_v = 1 \ge 1\)。
步骤1：寻找增广路径
目标是找到一个非匹配顶点 u，并以它为起点，搜索一条到另一个非匹配顶点 v 的交替路径。
在搜索过程中，我们只考虑满足 “等式边” 条件的边，即满足 \(y_u + y_v = 1\) 的边 e = (u, v)。这是由原始互补松弛条件引导的，因为我们希望最终能通过增广操作，使匹配边都满足这个条件。
搜索可以使用修改过的BFS或DFS（如匈牙利树算法中那样）来寻找从非匹配顶点出发的交替路径。
步骤2：判断与处理
- 情况A：找到增广路径。假设找到路径 \(u - ... - v\)。
- 对路径进行增广操作：路径上的边状态取反。匹配 M 的大小加1。
- 增广后，路径上所有边（现在都是匹配边）自然满足 \(y_u + y_v = 1\)（因为搜索时只用了等式边）。互补松弛条件得以维持。
- 返回步骤1，尝试寻找下一条增广路径。
- 情况B：未找到增广路径。这意味着从当前所有非匹配顶点出发，都无法通过等式边到达另一个非匹配顶点。
- 此时，我们需要调整对偶变量，以“创造”出新的等式边，从而可能发现新的增广路。
- 设搜索过程中访问过的顶点集合为 S（从非匹配顶点 u 出发能通过交替路到达的顶点）。
- 计算一个调整量 \(\delta\)：
\[ \delta = \min \{ y_u + y_v - 1 \ | \ u \in S, v \notin S, (u, v) \in E \} \]
这个 $\delta$ 是跨越搜索边界 S 的边中，与等式条件（=1）的最小差距。由于未找到增广路，所有从 S 到 V\S 的边都不是等式边，所以 $y_u+y_v > 1$，从而 $\delta > 0$。
* **对偶变量调整**：
* 对于 S 中的顶点：$y_v := y_v - \delta$
* 对于 V\S 中的顶点：$y_v := y_v + \delta$
* **调整效果**：
1. S 内部的边，两个端点 y 值一减一加，和不变，仍满足约束。
2. S 外部的边，和不变。
3. **关键**：对于跨越 S 边界的边 (u∈S, v∉S)，其和 $y_u+y_v$ 减少了 $\delta$。根据 $\delta$ 的定义，至少有一条这样的边变成了等式边 ($y_u+y_v=1$)，从而可以被加入后续的搜索中。
4. 对偶目标函数值 $\sum y_v$ 的变化为 $(|V\S| - |S|)\delta$。由于 S 中非匹配顶点和匹配顶点通常是成对出现的（除了起点），且搜索停止时 S 的结构，通常能保证 $|V\S| > |S|$，因此对偶目标值增加，符合对偶最小化的趋势。
* 调整对偶变量后，返回步骤1，继续在更新后的等式边图中搜索。
步骤3：算法终止
当无法找到任何增广路径，并且无法通过调整对偶变量创造出新的增广可能性时（实际上，当所有与 S 相连的边都已无法减少和时），算法终止。
定理：当算法终止时，当前匹配 M 是最大匹配，并且当前的对偶解 y 是线性规划对偶问题的一个可行解。根据互补松弛条件，它们分别是原始松弛问题和对偶问题的最优解。由于 M 是整数解，它也就是原整数规划问题（即最大匹配问题）的最优解。
总结
本示例展示了如何将图的最大匹配问题建模为线性规划，并利用其松弛后的对偶理论，导出了经典的增广路算法。该算法本质上是一个原始-对偶算法：它在组合层面维护一个原始的整数可行解（匹配 M），同时在连续层面维护一个对偶可行解（顶点势能 y），并通过不断调整对偶解来寻找满足互补松弛条件的原始最优解。这个框架深刻揭示了线性规划对偶理论与组合优化经典算法之间的内在联系。