基于线性规划的图顶点覆盖问题求解示例 题目描述 考虑一个无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集合，\( E \) 是边集合。图顶点覆盖问题要求找到一个最小的顶点子集 \( C \subseteq V \)，使得图中的每条边至少有一个端点属于 \( C \)。若将顶点覆盖问题建模为整数规划，其目标函数和约束条件均为线性，但变量需取整数值。本问题要求通过线性规划松弛和舍入策略，近似求解最小顶点覆盖问题。 解题过程 整数规划建模 对每个顶点 \( i \in V \)，引入二元变量 \( x_ i \)： \( x_ i = 1 \) 表示顶点 \( i \) 被选入覆盖集 \( C \)； \( x_ i = 0 \) 表示未被选中。 目标是最小化覆盖集大小： \[ \min \sum_ {i \in V} x_ i \] 约束条件为每条边至少有一个端点被覆盖：对每条边 \( (i, j) \in E \)， \[ x_ i + x_ j \geq 1 \] 且 \( x_ i \in \{0, 1\} \)。 线性规划松弛 将整数约束松弛为连续约束： \[ 0 \leq x_ i \leq 1 \quad \forall i \in V \] 得到线性规划问题： \[ \min \sum_ {i \in V} x_ i \quad \text{s.t.} \quad x_ i + x_ j \geq 1 \ \forall (i,j) \in E, \ 0 \leq x_ i \leq 1 \] 求解线性规划 使用单纯形法或内点法求解松弛后的线性规划，得到最优解 \( x^* \)。由于约束矩阵是全单模的（对于二分图），线性规划解自动为整数解。但一般图中，\( x^* \) 可能是分数解。 舍入策略 采用简单的舍入规则： \[ \hat{x}_ i = \begin{cases} 1 & \text{if } x_ i^* \geq 0.5 \\ 0 & \text{otherwise} \end{cases} \] 即：若顶点对应的线性规划解值不小于 0.5，则将其选入覆盖集。 可行性验证 对任意边 \( (i, j) \in E \)，由线性规划约束 \( x_ i^* + x_ j^* \geq 1 \) 可知，\( x_ i^* \) 和 \( x_ j^* \) 中至少有一个不小于 0.5。因此舍入后至少有一个顶点被选中，覆盖该边。 近似比分析 设 \( \text{OPT} {\text{LP}} \) 是线性规划最优值，\( \text{OPT} {\text{IPC}} \) 是整数规划最优值。由于松弛性质，\( \text{OPT} {\text{LP}} \leq \text{OPT} {\text{IPC}} \)。 舍入后目标值满足： \[ \sum_ {i \in V} \hat{x} i \leq 2 \sum {i \in V} x_ i^* = 2 \cdot \text{OPT} {\text{LP}} \leq 2 \cdot \text{OPT} {\text{IPC}} \] 因此该算法是2-近似算法。 总结 通过线性规划松弛和舍入，可在多项式时间内得到最小顶点覆盖的2-近似解，适用于大规模图问题。该方法平衡了计算效率与解的质量。