基于线性规划的图最小边覆盖问题求解示例

题目描述
给定一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集（\(|V| = n\)），\(E\) 是边集（\(|E| = m\)）。最小边覆盖问题要求找到一个边集 \(C \subseteq E\)，使得图中每个顶点至少与 \(C\) 中的一条边相邻（即被覆盖），且 \(C\) 的边数最小。注意：如果图中存在孤立顶点（度数为0的顶点），则问题无解。本题假设图无孤立顶点。

解题过程

1. 问题分析

   • 边覆盖的定义：边集 \(C\) 覆盖所有顶点，即每个顶点至少是 \(C\) 中某条边的端点。
   • 关键观察：最小边覆盖与图的最大匹配密切相关。通过Konig定理的推广，最小边覆盖大小等于 \(n - \nu(G)\)，其中 \(\nu(G)\) 是图的最大匹配大小。但本节直接通过线性规划建模求解。

2. 线性规划建模

   • 定义决策变量：对每条边 \(e \in E\)，引入二进制变量 \(x_e \in \{0, 1\}\)，表示边 \(e\) 是否被选入覆盖集 \(C\)（1表示选中）。
   • 目标函数：最小化覆盖集的大小，即

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

• 约束条件：每个顶点必须被至少一条选中的边覆盖。对每个顶点 \(v \in V\)，其相邻边的变量和至少为1：

\[ \sum_{e \in \delta(v)} x_e \geq 1 \quad \forall v \in V \]

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

• 完整整数线性规划模型：

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

3. 线性规划松弛
   • 将整数约束松弛为连续约束：

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

• 松弛后的线性规划问题为：

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

• 该线性规划的最优解可能包含分数值，但可以证明其基本可行解是整数解（因为约束矩阵是全单模的），因此直接求解线性规划即可得到原问题的最优解。

4. 求解步骤

   • 步骤1：检查图中是否有孤立顶点。若有，则问题无解，算法终止。
   • 步骤2：构建上述线性规划模型，使用单纯形法或内点法求解。
   • 步骤3：分析解的性质。由于全单模性，解 \(x_e^*\) 自动为整数（0或1），直接得到最小边覆盖集 \(C = \{ e \in E \mid x_e^* = 1 \}\)。
   • 步骤4：验证解的正确性，确保每个顶点被覆盖且边数最小。

5. 示例演示

   • 考虑图 \(G\) 有顶点集 \(V = \{1, 2, 3, 4\}\)，边集 \(E = \{(1,2), (2,3), (3,4), (4,1)\}\)（四边形）。
   • 建模：变量 \(x_{12}, x_{23}, x_{34}, x_{41}\)，目标最小化 \(x_{12} + x_{23} + x_{34} + x_{41}\)。
     • 约束：
       • 顶点1: \(x_{12} + x_{41} \geq 1\)
       • 顶点2: \(x_{12} + x_{23} \geq 1\)
       • 顶点3: \(x_{23} + x_{34} \geq 1\)
       • 顶点4: \(x_{34} + x_{41} \geq 1\)
   • 求解得 \(x_{12} = 1, x_{23} = 0, x_{34} = 1, x_{41} = 0\)（或对称解），边覆盖大小为2，覆盖集为 \(\{(1,2), (3,4)\}\)。
   • 验证：所有顶点均被覆盖，且无法用少于2条边覆盖。

6. 算法复杂度

   • 线性规划的变量数为 \(m\)，约束数为 \(n\)，使用内点法可在多项式时间 \(O((m+n)^{3.5}L)\) 内求解（\(L\) 为输入规模）。
   • 实际中常利用全单模性直接调用线性规划求解器。

总结
最小边覆盖问题可通过线性规划建模求解，松弛后的线性规划具有整数最优解，无需额外整数规划技巧。该方法适用于任意无孤立顶点的图，并保证最优性。