其中 $ \delta^+(u_{out}) $ 表示从 $ u_{out} $ 出发的边集。类似地，对于所有右部顶点 $ v_{in} \in W $：

    其中 $ \delta^-(v_{in}) $ 表示指向 $ v_{in} $ 的边集。
2.  **整数约束**：

基于线性规划的图最小路径覆盖问题的DAG分解与算法设计示例 1. 问题描述 我们考虑一个有向无环图（Directed Acyclic Graph, DAG）中的最小路径覆盖问题。给定一个DAG \( G = (V, E) \)，其中 \( V \) 是顶点集，\( E \) 是有向边集。一条路径覆盖是G中一组顶点不相交（即任意两条路径不共享顶点）的有向路径，这组路径覆盖了图G中的所有顶点。最小路径覆盖问题是寻找一个路径覆盖，使得路径的数量最少。 2. 问题理解与关键观察 目标 ：用尽可能少的、顶点不相交的路径，覆盖所有顶点。 核心难点 ：路径必须是顶点不相交的，且必须遵循DAG的有向边方向。 关键观察（分解定理） ：对于DAG，最小路径覆盖问题可以转化为二分图最大匹配问题。这个转化是解决问题的核心。 步骤1（图拆分） ：将原DAG G中的每个顶点v拆分成两个顶点：一个左部顶点 \( v_ {out} \)（代表v作为路径的起点或中间节点的“流出”角色），一个右部顶点 \( v_ {in} \)（代表v作为路径的终点或中间节点的“流入”角色）。这样构造一个二分图 \( B = (U, W, E') \)，其中 \( U = \{v_ {out} | v \in V\} \)， \( W = \{v_ {in} | v \in V\} \)。 步骤2（边对应） ：对于原图G中的每一条有向边 \( (u, v) \in E \)，我们在二分图B中添加一条从 \( u_ {out} \) 到 \( v_ {in} \) 的边。 步骤3（定理表述） ：DAG G的最小路径覆盖的路径数等于 \( |V| \) 减去二分图B的最大匹配的基数。即，如果最大匹配的大小为 \( M \)，则最小路径覆盖包含 \( |V| - M \) 条路径。 3. 基于线性规划的建模 我们可以为转化后的二分图最大匹配问题建立一个整数线性规划（ILP）模型，然后松弛为线性规划（LP）来求解，并证明其最优解是整数的。 决策变量 ：对于二分图B中的每一条边 \( e = (u_ {out}, v_ {in}) \in E' \)，定义一个变量 \( x_ e \in \{0, 1\} \)。\( x_ e = 1 \) 表示这条边被选入匹配中，\( x_ e = 0 \) 表示未被选中。 目标函数 ：最大化匹配的基数，即最大化被选中边的数量。 \[ \text{最大化} \quad \sum_ {e \in E'} x_ e \] 约束条件 ： 顶点约束 ：在二分图中，每个顶点最多只能与一条选中的边关联（匹配的定义）。对于所有左部顶点 \( u_ {out} \in U \)： \[ \sum_ {e \in \delta^+(u_ {out})} x_ e \le 1 \] 其中 \( \delta^+(u_ {out}) \) 表示从 \( u_ {out} \) 出发的边集。类似地，对于所有右部顶点 \( v_ {in} \in W \)： \[ \sum_ {e \in \delta^-(v_ {in})} x_ e \le 1 \] 其中 \( \delta^-(v_ {in}) \) 表示指向 \( v_ {in} \) 的边集。 整数约束 ： \[ x_ e \in \{0, 1\}, \quad \forall e \in E' \] 线性规划松弛 ：将整数约束松弛为 \( 0 \le x_ e \le 1 \)。这个线性规划的最优解一定是整数解（因为其约束矩阵是全单模矩阵），所以可以直接用单纯形法等LP求解器得到原ILP（即最大匹配）的最优解。 4. 从匹配解构造路径覆盖 假设我们求解上述LP得到了一个最大匹配 \( M^* \)（大小为 \( |M^ | \)）。我们可以通过以下步骤从 \( M^ \) 还原出原DAG G中的最小路径覆盖： 初始化 ：在G中，将每个顶点都视为一条独立的单顶点路径。此时有 \( |V| \) 条路径。 合并路径 ：对于匹配 \( M^* \) 中的每一条边 \( (u_ {out}, v_ {in}) \)（对应原图G中的边 \( (u, v) \)），它表示在覆盖路径中，顶点u是顶点v的直接前驱。因此，我们可以将u所在的路径的末尾与v所在的路径的开头连接起来（因为DAG无环，这总是可行的），从而将两条路径合并为一条。每进行一次这样的合并，路径总数减少1。 构造结果 ：由于 \( M^* \) 中有 \( |M^ | \) 条匹配边，我们恰好可以进行 \( |M^ | \) 次合并。最终得到的路径集合就是最小路径覆盖，路径数量为 \( |V| - |M^* | \)。 5. 循序渐进示例 考虑一个简单的DAG G，有顶点集 \( V = \{1, 2, 3, 4\} \)，边集 \( E = \{(1,2), (1,3), (2,4), (3,4)\} \)。 步骤1：构建二分图B 。 拆分顶点：\( U = \{1_ {out}, 2_ {out}, 3_ {out}, 4_ {out}\} \)， \( W = \{1_ {in}, 2_ {in}, 3_ {in}, 4_ {in}\} \)。 添加边：\( E' = \{(1_ {out},2_ {in}), (1_ {out},3_ {in}), (2_ {out},4_ {in}), (3_ {out},4_ {in})\} \)。 步骤2：建立并求解线性规划 。 变量：\( x_ {12}, x_ {13}, x_ {24}, x_ {34} \) 分别对应上述四条边。 目标：最大化 \( x_ {12} + x_ {13} + x_ {24} + x_ {34} \)。 约束： 对于左部：\( 1_ {out}: x_ {12}+x_ {13} \le 1 \); \( 2_ {out}: x_ {24} \le 1 \); \( 3_ {out}: x_ {34} \le 1 \); \( 4_ {out}: \text{（无出边）} \)。 对于右部：\( 1_ {in}: \text{（无入边）} \); \( 2_ {in}: x_ {12} \le 1 \); \( 3_ {in}: x_ {13} \le 1 \); \( 4_ {in}: x_ {24}+x_ {34} \le 1 \)。 边界：\( 0 \le x_ {ij} \le 1 \)。 求解（如单纯形法）：得到一个最优整数解，例如 \( x_ {12}=1, x_ {13}=0, x_ {24}=1, x_ {34}=0 \)。最大匹配大小 \( |M^* | = 2 \)。 步骤3：构造最小路径覆盖 。 初始路径：\{1\}, \{2\}, \{3\}, \{4\}（4条）。 根据匹配边 \( (1_ {out},2_ {in}) \)（对应G中边(1,2)），合并路径\{1\}和\{2\}，得到\{1->2\}。路径变为：\{1->2\}, \{3\}, \{4\}（3条）。 根据匹配边 \( (2_ {out},4_ {in}) \)（对应G中边(2,4)），合并路径\{1->2\}和\{4\}，得到\{1->2->4\}。路径变为：\{1->2->4\}, \{3\}（2条）。 最终最小路径覆盖为：\{1->2->4\} 和 \{3\}。路径数为 \( 4 - 2 = 2 \)。 6. 算法总结与要点 算法步骤 ： 给定DAG G=(V, E)，构造对应的二分图 B=(U, W, E')。 为B上的最大匹配问题建立LP模型（或直接使用匈牙利算法等组合算法求解最大匹配，其本质也对应于求解该LP）。 求解该LP，得到最大匹配 \( M^* \)。 根据 \( M^* \) 中的边，通过并查集或直接遍历的方式，在原图G中合并路径，得到最小路径覆盖。 关键点 ：理解DAG最小路径覆盖与二分图最大匹配的等价性是核心。线性规划在这里提供了一个形式化的建模和求解框架，并且由于问题的特殊结构（全单模性），LP松弛能得到整数最优解，确保了正确性。该算法的时间复杂度主要由求解最大匹配的算法决定（例如，使用基于增广路的算法为 \( O(\sqrt{|V|}|E|) \)，使用LP求解器则依赖于具体实现）。