基于线性规划的图边覆盖问题求解示例
题目描述
在图论中，边覆盖是指边的集合，使得图中每个顶点至少与该集合中的一条边相邻。最小边覆盖问题要求找到一个边数最少的边覆盖。给定一个无向图 \(G = (V, E)\)（假设无孤立顶点），每条边 \(e \in E\) 有一个决策变量 \(x_e \in \{0, 1\}\) 表示是否选择该边，目标是最小化所选边的总数，同时满足每个顶点至少被一条边覆盖。该问题可以通过线性规划结合图的性质高效求解。
解题过程
1. 问题建模
设图 \(G\) 有 \(n = |V|\) 个顶点和 \(m = |E|\) 条边。定义决策变量：
\[x_e = \begin{cases} 1 & \text{选择边 } e \\ 0 & \text{不选择边 } e \end{cases} \]
目标函数是最小化所选边的数量：
\[\min \sum_{e \in E} x_e \]
约束条件要求每个顶点至少被一条边覆盖。对于顶点 \(v\)，其关联的边集合为 \(\delta(v)\)（即与 \(v\) 相连的边），约束为：
\[\sum_{e \in \delta(v)} x_e \geq 1 \quad \forall v \in V \]
此外，变量需满足整数约束：
\[x_e \in \{0, 1\} \quad \forall e \in E \]
这是一个整数线性规划（ILP）问题。
2. 线性规划松弛
将整数约束松弛为连续约束：
\[0 \leq x_e \leq 1 \quad \forall e \in E \]
得到线性规划松弛问题：
\[\min \sum_{e \in E} x_e \quad \text{s.t.} \quad \sum_{e \in \delta(v)} x_e \geq 1 \ \forall v \in V, \ 0 \leq x_e \leq 1 \]
由于约束矩阵是全单模的（无向图关联矩阵），线性规划松弛的最优解一定是整数解（即 \(x_e \in \{0, 1\}\)），因此直接求解该线性规划即可得到原问题的最优解。
3. 算法步骤
步骤 1：构造线性规划模型
- 列出所有顶点约束：对每个顶点 \(v\)，其约束为关联边的变量之和 ≥ 1。
- 添加边界约束 \(0 \leq x_e \leq 1\)。
步骤 2：求解线性规划
使用单纯形法或内点法求解松弛后的线性规划，得到最优解 \(x^*\)。
步骤 3：验证整数性
由于全单模性，解 \(x^*\) 自动为整数（0 或 1）。若出现非整数解（理论上不可能），需分支定界法处理，但本例中无需此步骤。
步骤 4：构造边覆盖
集合 \(C = \{ e \in E \mid x_e^* = 1 \}\) 即为最小边覆盖。
4. 示例演示
考虑一个简单图：顶点集 \(V = \{1, 2, 3\}\)，边集 \(E = \{a=(1,2), b=(2,3), c=(1,3)\}\)。
线性规划模型：
\[\min x_a + x_b + x_c \]
约束：
- 顶点 1: \(x_a + x_c \geq 1\)
- 顶点 2: \(x_a + x_b \geq 1\)
- 顶点 3: \(x_b + x_c \geq 1\)
- \(0 \leq x_a, x_b, x_c \leq 1\)
求解：
通过单纯形法得到最优解 \(x_a = 1, x_b = 0, x_c = 1\)（或对称解 \(x_a = 0, x_b = 1, x_c = 1\)），目标函数值为 2。
边覆盖 \(C = \{a, c\}\) 覆盖所有顶点（边 \(a\) 覆盖顶点 1 和 2，边 \(c\) 覆盖顶点 1 和 3）。
5. 与顶点覆盖的关系
根据图论定理：最小边覆盖大小 = 顶点数 - 最大匹配大小。
- 上例中，顶点数 \(n=3\)，最大匹配大小为 1（如匹配 \(\{a\}\)），故最小边覆盖大小 = \(3-1=2\)，与线性规划结果一致。
总结
最小边覆盖问题可通过线性规划松弛精确求解，无需整数规划技巧。关键在于利用图的全单模性保证整数解，并结合图论定理验证结果。