基于线性规划的图最大匹配问题求解示例

题目描述
图最大匹配问题是指在一个无向图 \(G = (V, E)\) 中，寻找一个边集 \(M \subseteq E\)，使得任意两条边不共享公共顶点，且 \(M\) 包含的边数尽可能多。例如，在招聘场景中，顶点表示求职者和职位，边表示求职者能胜任某职位，目标是最大化匹配数量。该问题可通过线性规划建模并求解。

解题过程

1. 问题建模

• 定义决策变量 \(x_e\) 对每条边 \(e \in E\)：

\[ x_e = \begin{cases} 1 & \text{边 } e \text{ 被选入匹配集 } M \\ 0 & \text{否则} \end{cases} \]

• 目标函数：最大化匹配的边数，即

\[ \max \sum_{e \in E} x_e \]

• 约束条件：每个顶点最多被一条边覆盖。对每个顶点 \(v \in V\)：

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

其中 \(\delta(v)\) 表示与顶点 \(v\) 相连的边集。

2. 线性规划松弛
由于整数规划求解困难，将 \(x_e \in \{0,1\}\) 松弛为连续变量：

\[0 \leq x_e \leq 1 \quad (\forall e \in E) \]

此时问题变为线性规划，可用单纯形法等求解。虽然松弛后解可能非整数，但图匹配问题的线性规划具有整数最优解性质（由图的二分性或其他结构保证），因此松弛解即原问题最优解。

3. 求解步骤
以简单图为例（如图1）：

顶点集: {1, 2, 3, 4}  
边集: (1,2), (1,3), (2,4), (3,4)

• 建模：
  变量：\(x_{12}, x_{13}, x_{24}, x_{34}\)
  目标：\(\max x_{12} + x_{13} + x_{24} + x_{34}\)
  约束：

\[ \begin{align*} \text{顶点1:} & \quad x_{12} + x_{13} \leq 1 \\ \text{顶点2:} & \quad x_{12} + x_{24} \leq 1 \\ \text{顶点3:} & \quad x_{13} + x_{34} \leq 1 \\ \text{顶点4:} & \quad x_{24} + x_{34} \leq 1 \\ x_e \geq 0 \end{align*} \]

• 求解松弛问题：
  使用单纯形法或工具求解，得最优解 \(x_{12} = 1, x_{34} = 1\)，其他变量为0，目标函数值为2。
  由于解为整数，直接对应原问题匹配：边集 \(\{(1,2), (3,4)\}\)。

4. 一般图的处理
若图非二分图，线性规划松弛可能产生非整数解（如半整数解）。此时需添加奇环约束（Odd Cycle Constraints）：
对任意长度为奇数的环 \(C\)，添加

\[\sum_{e \in C} x_e \leq \frac{|C|-1}{2} \]

通过迭代添加此类约束，可逐步逼近整数解（使用割平面法）。

5. 算法意义
线性规划方法为匹配问题提供了理论保证（如二分图的最优性），并启发了实际算法（如匈牙利算法）。对于复杂图，结合分解技巧可提升求解效率。

总结
通过线性规划建模和松弛，结合图论性质，可高效求解最大匹配问题。该方法凸显了连续优化在离散问题中的强大作用。