有向无环图（DAG）的最小路径覆盖（不相交）问题
字数 3297 2025-12-18 20:46:46
有向无环图（DAG）的最小路径覆盖（不相交）问题
今天我们来讨论一个经典问题：在有向无环图（DAG） 中，如何用最少的互不相交的路径覆盖图中所有顶点。每条路径可以是一个或多个顶点，但路径之间不能共享顶点。这个问题被称为 DAG的最小（顶点）不相交路径覆盖。
问题定义
给定一个有向无环图 \(G = (V, E)\)，目标是找到一组数量最少的路径，满足：
- 每条路径是图 \(G\) 中的一条有向路径（顶点序列 \(v_1 \to v_2 \to \dots \to v_k\)，且相邻顶点间有边）。
- 这些路径覆盖了 \(V\) 中的所有顶点，即每个顶点恰好出现在一条路径中（不相交）。
- 路径的数量最小。
示例：
考虑下图（一个DAG）：
顶点：1, 2, 3, 4
边：1 → 2, 1 → 3, 2 → 4, 3 → 4
一种覆盖是所有顶点单独作为一条路径，共4条。但更优的方案是：
- 路径1: 1 → 2 → 4
- 路径2: 3
或者： - 路径1: 1 → 3 → 4
- 路径2: 2
这样只需2条路径。
核心思想：转化为二分图最大匹配
这个问题可以通过构建一个二分图，并求其最大匹配来解决。步骤如下：
步骤1：构建二分图模型
- 将原DAG \(G\) 的每个顶点 \(v\) 拆分成两个顶点：左部顶点 \(v_{\text{out}}\) 和右部顶点 \(v_{\text{in}}\)。
- 左部对应“路径的起点”或“前驱”，右部对应“路径的终点”或“后继”。
- 对于原图中的每条有向边 \(u \to v\)，在二分图中添加一条从 \(u_{\text{out}}\) 到 \(v_{\text{in}}\) 的边。
- 这样，二分图 \(B = (L, R, E_B)\) 就构建好了，其中 \(L = \{v_{\text{out}} \mid v \in V\}\)，\(R = \{v_{\text{in}} \mid v \in V\}\)，且 \(|L| = |R| = |V|\)。
为什么这样建模？
- 在DAG中，一条路径可以看作一连串的边连接。
- 在二分图中，匹配边 \(u_{\text{out}} \to v_{\text{in}}\) 表示在原图中，顶点 \(u\) 是 \(v\) 的直接前驱（即 \(u \to v\) 在路径中）。
- 一个匹配对应一组原图中的边连接关系，这些连接关系可以组合成若干条路径。
步骤2：理解匹配与路径覆盖的关系
关键定理（Dilworth定理的一个推论）：
最小路径覆盖数 = |V| - 最大匹配数
直观解释：
- 初始时，假设每个顶点自成一条路径，那么路径数 = |V|。
- 每当我们在二分图中找到一条匹配边 \(u_{\text{out}} \to v_{\text{in}}\)，就相当于将 \(u\) 所在路径和 \(v\) 所在路径合并（因为 \(u\) 变成了 \(v\) 的前驱，两条路径首尾相接成一条）。
- 一个匹配对应一组合并操作。每增加一条匹配边，路径数就减少1（因为两条路径合并为一条）。
- 因此，最大匹配使得合并次数最多，从而路径数最少。
步骤3：求解二分图最大匹配
二分图最大匹配可以用匈牙利算法（\(O(VE)\)）或更高效的Hopcroft-Karp算法（\(O(E\sqrt{V})\)）求解。这里我们简述匈牙利算法的思路：
- 初始化所有匹配为空。
- 对左部每个顶点 \(u\)，尝试为它寻找一个右部顶点 \(v\) 进行匹配。
- 寻找过程使用DFS：如果 \(v\) 未被匹配，则直接匹配；如果 \(v\) 已匹配，则尝试为 \(v\) 的原配左部顶点寻找新的匹配（递归），即“增广”。
- 如果能找到一条增广路径（交替路径），则匹配数增加1。
步骤4：从匹配重构路径
得到最大匹配后，我们可以还原出最小路径覆盖：
- 在匹配中，每条边 \(u_{\text{out}} \to v_{\text{in}}\) 对应原图中 \(u\) 是 \(v\) 的直接前驱。
- 根据匹配边，可以构建一个前驱关系图（仍是原图的一个子图）：
- 对于每个右部顶点 \(v_{\text{in}}\)，如果它被匹配到某个 \(u_{\text{out}}\)，则 \(u\) 是 \(v\) 的前驱。
- 未被匹配的右部顶点对应一条路径的起点（因为没有前驱）。
- 未被匹配的左部顶点对应一条路径的终点（因为没有后继）。
- 从前驱关系出发，可以DFS或直接追踪出所有路径。
完整算法流程
- 输入有向无环图 \(G = (V, E)\)。
- 构建二分图 \(B\)：
- 左部顶点集：\(\{v_{\text{out}} \mid v \in V\}\)
- 右部顶点集：\(\{v_{\text{in}} \mid v \in V\}\)
- 对每条边 \((u, v) \in E\)，在 \(B\) 中添加边 \((u_{\text{out}}, v_{\text{in}})\)。
- 在二分图 \(B\) 上求最大匹配 \(M\)（使用匈牙利算法或Hopcroft-Karp算法）。
- 最小路径覆盖数 = \(|V| - |M|\)。
- 根据匹配 \(M\) 还原出具体路径：
- 初始化每个顶点为单独路径。
- 对于匹配边 \((u_{\text{out}}, v_{\text{in}}) \in M\)，将 \(u\) 所在路径的末尾与 \(v\) 所在路径的开头连接。
举例说明
考虑DAG：
顶点：{1, 2, 3, 4}
边：1→2, 1→3, 2→4, 3→4
- 构建二分图：
- 左部：{1_out, 2_out, 3_out, 4_out}
- 右部：{1_in, 2_in, 3_in, 4_in}
- 边：(1_out,2_in), (1_out,3_in), (2_out,4_in), (3_out,4_in)
- 求最大匹配。一种最大匹配是 {(1_out,2_in), (3_out,4_in)}，大小|M|=2。
- 最小路径覆盖数 = 4 - 2 = 2。
- 还原路径：
- 匹配边1_out→2_in：表示1→2。
- 匹配边3_out→4_in：表示3→4。
- 顶点1_in和4_out未匹配，对应路径起点1和终点4？不，要小心：未匹配的右部顶点（即没有被作为“后继”匹配的）是路径的起点。这里右部未匹配的是1_in和3_in？我们检查：
- 右部顶点2_in匹配到1_out，所以2有前驱1。
- 右部顶点4_in匹配到3_out，所以4有前驱3。
- 右部顶点1_in和3_in未被匹配，所以1和3是路径起点。
- 左部顶点1_out和3_out已匹配，2_out和4_out未匹配，所以2和4是路径终点？更准确地说，我们从起点开始追踪：
从起点1：1→2（因为匹配1_out→2_in），然后2是终点吗？看2_out未匹配，所以2没有后继，路径结束：1→2。
从起点3：3→4（匹配3_out→4_in），然后4_out未匹配，路径结束：3→4。
- 因此两条路径：1→2 和 3→4，覆盖所有顶点。
复杂度分析
- 二分图有 \(2|V|\) 个顶点，最多 \(|E|\) 条边（因为原图每条边对应一条二分图边）。
- 使用匈牙利算法：\(O(VE)\)。
- 使用Hopcroft-Karp算法：\(O(E\sqrt{V})\)。
因为通常 \(|E| \leq |V|^2\)，所以算法是多项式时间的。
扩展与变体
- 如果允许路径相交（即顶点可以被多条路径共享），则问题变为“最小边覆盖”或“最小链覆盖”，可以用传递闭包后转化为二分图匹配。
- 如果图不是DAG，问题变为NP-Hard（因为可以归约到哈密顿路径问题）。
这个算法巧妙地将路径覆盖问题转化为匹配问题，是图论中一个经典的二分图应用。