基于线性规划的图最小边覆盖问题求解示例 问题描述 最小边覆盖问题是在无向图 \( G = (V, E) \) 中寻找边数最少的边子集 \( C \subseteq E \)，使得图中每个顶点至少与 \( C \) 中的一条边关联。该问题可转化为线性规划模型求解。例如，对图 \( G \) 有顶点集 \( V = \{1, 2, 3, 4\} \) 和边集 \( E = \{(1,2), (2,3), (3,4), (1,4)\} \)，目标是选择最少的边覆盖所有顶点。 关键定义与建模 决策变量 ：对每条边 \( e \in E \)，定义二进制变量 \( x_ e \in \{0, 1\} \)，若 \( x_ e = 1 \) 表示边 \( e \) 被选入覆盖集 \( C \)。 目标函数 ：最小化边数，即 \( \min \sum_ {e \in E} x_ e \)。 约束条件 ：每个顶点 \( v \in V \) 必须被至少一条边覆盖。对顶点 \( v \)，其关联边的变量和需满足 \( \sum_ {e \in \delta(v)} x_ e \geq 1 \)，其中 \( \delta(v) \) 表示与 \( v \) 相连的边集。 线性规划松弛 ：将整数约束 \( x_ e \in \{0,1\} \) 松弛为 \( 0 \leq x_ e \leq 1 \)，得到线性规划问题： \[ \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} \] 求解步骤 构建实例模型 ：对示例图，变量为 \( x_ {12}, x_ {23}, x_ {34}, x_ {14} \)。约束为： 顶点1: \( x_ {12} + x_ {14} \geq 1 \) 顶点2: \( x_ {12} + x_ {23} \geq 1 \) 顶点3: \( x_ {23} + x_ {34} \geq 1 \) 顶点4: \( x_ {14} + x_ {34} \geq 1 \) 目标函数：\( \min x_ {12} + x_ {23} + x_ {34} + x_ {14} \)。 求解线性规划松弛 ：使用单纯形法或内点法求解。本例中，最优解为 \( x_ {12} = 0.5, x_ {23} = 0.5, x_ {34} = 0.5, x_ {14} = 0.5 \)，目标值 \( = 2 \)。 整数化处理 ：松弛解可能含小数，需通过舍入或分支定界法得整数解。观察约束的系数矩阵为全单模矩阵（因图是二分图），松弛解自动为整数。本例中，实际最优整数解可通过枚举验证：选择边 \( \{(1,2), (3,4)\} \) 或 \( \{(2,3), (1,4)\} \)，边数均为 2。 最优性验证 ：根据König定理（在二分图中，最小边覆盖数 = 顶点数 - 最大匹配数），本例中顶点数 \( |V|=4 \)，最大匹配数为 2（如匹配 \( \{(1,2), (3,4)\} \)），故最小边覆盖数 \( = 4 - 2 = 2 \)，与线性规划结果一致。 总结 最小边覆盖问题可通过线性规划建模求解，松弛模型在特定条件下（如二分图）可直接得整数最优解。一般图中，需结合整数规划方法确保解可行性。