基于线性规划的图最小路径覆盖问题求解示例 题目描述 考虑一个有向无环图（DAG）G = (V, E)，其中V是顶点集合，E是有向边集合。最小路径覆盖问题要求找到最少数量的顶点不相交的路径，使得这些路径覆盖图中的所有顶点（即每个顶点恰好出现在一条路径上）。例如，对于有向边集{(1,2), (2,3), (4,5)}的图，最小路径覆盖为2（路径1→2→3和路径4→5）。 解题过程 问题分析 最小路径覆盖可转化为二分图最大匹配问题。将原图G的每个顶点v拆分为两个顶点vₐ（在二分图左侧）和v_ b（在右侧）。对于原图中的每条有向边(u,v) ∈ E，在二分图中添加一条从uₐ到v_ b的边。此时，原图的最小路径覆盖数等于|V|减去二分图的最大匹配数。 线性规划建模 定义决策变量x_ e表示边e是否被选中（1为选中，0为否）。目标是最小化路径数量，即最小化未匹配的顶点数。通过以下约束确保每个顶点最多有一条入边和一条出边： 目标函数：minimize ∑ {v∈V} (1 - ∑ {e∈δ⁺(v)} x_ e) 其中δ⁺(v)表示以v为起点的边集。 约束条件： a. 每个顶点最多一条出边：∑ {e∈δ⁺(v)} x_ e ≤ 1, ∀v∈V b. 每个顶点最多一条入边：∑ {e∈δ⁻(v)} x_ e ≤ 1, ∀v∈V c. 变量范围：x_ e ≥ 0, ∀e∈E 由于约束矩阵是全单模的，线性规划松弛的解自动为整数。 求解步骤 步骤1 ：将原图转换为二分图，构建上述线性规划模型。 步骤2 ：使用单纯形法求解线性规划，得到最优解x_ e* 。 步骤3 ：根据x_ e* 的值确定选中的边，这些边构成若干条路径。未被选中的边对应的顶点即为路径起点。 步骤4 ：路径数量等于顶点数减去选中边的总数。 示例演示 设图G有顶点集V={1,2,3,4}，边集E={(1,2), (2,3), (1,3), (4,2)}。 二分图匹配：最大匹配为2（例如边(1,2)和(4,3)）。 最小路径覆盖数 = 4 - 2 = 2，路径为1→2→3和4。 线性规划求解后，x_ (1,2)=1, x_ (2,3)=1, 其他边为0，得到相同结果。