有向无环图（DAG）的最小路径覆盖（Min Path Cover in DAG）问题
字数 2456 2025-12-14 22:04:06

有向无环图（DAG）的最小路径覆盖（Min Path Cover in DAG）问题

问题描述
我们给定一个有向无环图（Directed Acyclic Graph, DAG），其顶点集为 \(V\)，边集为 \(E\)。路径覆盖 是指图中一组不相交（即顶点不相交）的路径，使得图中每一个顶点都恰好出现在其中一条路径上。这里的“路径”可以是一个单顶点路径（即长度为0的路径）。最小路径覆盖 是覆盖所有顶点所需最少路径数量的路径覆盖。

我们的目标：给定一个 DAG，求出其最小路径覆盖的具体方案（或至少求出最少路径数）。

解题思路
这是一个经典问题，可以用二分图最大匹配来高效求解。核心思想是：

  • 将原 DAG 的每个顶点 \(v\) 拆成两个顶点：一个“出点”（在左部）、一个“入点”（在右部）。
  • 原图中的每条有向边 \(u \to v\) 对应二分图中的一条从左部的 \(u_{\text{out}}\) 到右部的 \(v_{\text{in}}\) 的边。
  • 在二分图中找到最大匹配，原图的最小路径覆盖数就等于顶点数减去最大匹配数。
  • 最后通过匹配关系可以还原出具体的路径覆盖方案。

详细步骤

步骤1：构建二分图模型
设原 DAG 的顶点数为 \(n\)。构建二分图 \(B = (X, Y, E_B)\)，其中：

  • \(X = \{x_1, x_2, \dots, x_n\}\) 对应原图每个顶点作为“路径起点”的可能性。
  • \(Y = \{y_1, y_2, \dots, y_n\}\) 对应原图每个顶点作为“路径终点”的可能性。
  • 对于原图的每条有向边 \((u, v)\)，在二分图中添加一条从 \(x_u\) 到 \(y_v\) 的边。

直观理解：如果我们在二分图中选择边 \((x_u, y_v)\)，意味着在原图中可以将顶点 \(u\) 和 \(v\) 连接在同一条路径上（即 \(v\) 是 \(u\) 的直接后继）。

步骤2：最大匹配与最小路径覆盖的关系

  • 在二分图 \(B\) 中的一个匹配，表示我们选择了若干条原图中的“连接关系”，将不同顶点“串联”到同一条路径上。
  • 关键性质：原图的一条路径覆盖对应二分图中的一个匹配，且路径数 = 顶点数 − 匹配边数。
    原因：初始时，每个顶点自成一个单点路径，共 \(n\) 条路径。每当二分图中选中一条匹配边 \((x_u, y_v)\)，我们就将 \(u\) 所在的路径和 \(v\) 所在的路径合并（即 \(v\) 所在的路径接到 \(u\) 所在路径的末尾），总路径数减少1。
  • 为了最小化路径数，我们需要最大化匹配边数。因此：

\[ \text{最小路径覆盖数} = n - \text{最大匹配数} \]

这里最大匹配是二分图 \(B\) 中的最大匹配。

步骤3：求解二分图最大匹配
二分图最大匹配可以用匈牙利算法（复杂度 \(O(nm)\)）或 Hopcroft–Karp 算法（复杂度 \(O(m\sqrt{n})\)）求解。
我们用邻接表存储二分图 \(B\)，然后运行最大匹配算法即可得到最大匹配的边集。

步骤4：还原具体路径
设最大匹配结果为：对于某些顶点 \(u\) 和 \(v\)，匹配边为 \((x_u, y_v)\)（表示 \(u \to v\) 的连接）。
我们需要从匹配关系还原出原图中的路径：

  1. 根据匹配边，构建一个数组 \(\text{next}[u]\) 表示在原图中顶点 \(u\) 的下一个顶点是 \(v\)（如果 \((x_u, y_v)\) 是匹配边），否则 \(\text{next}[u] = -1\)。
  2. 同时，构建一个数组 \(\text{prev}[v]\) 表示在原图中顶点 \(v\) 的前一个顶点是 \(u\)（如果 \((x_u, y_v)\) 是匹配边），否则 \(\text{prev}[v] = -1\)。
  3. 路径的起点是那些入度为0的顶点（在原图中没有前驱，即 \(\text{prev}[u] = -1\)）。从每个起点出发，沿着 \(\text{next}\) 数组走到终点（ \(\text{next}[u] = -1\) 的顶点），即可得到一条路径。
  4. 所有顶点都会被覆盖，且这些路径两两不相交（因为匹配是顶点不相交的）。

举例说明
考虑一个 DAG 有顶点 {1,2,3,4} 和边：1→2, 1→3, 2→4, 3→4。
构建二分图：

  • 左部 X = {x₁, x₂, x₃, x₄}，右部 Y = {y₁, y₂, y₃, y₄}。
  • 边：x₁→y₂, x₁→y₃, x₂→y₄, x₃→y₄。

求最大匹配（用匈牙利算法）：一个最大匹配是 {(x₁, y₂), (x₂, y₄)} 或 {(x₁, y₃), (x₃, y₄)}，匹配数为2。
则最小路径覆盖数 = 4 − 2 = 2。

以匹配 {(x₁, y₂), (x₂, y₄)} 为例：

  • next[1]=2, next[2]=4, prev[2]=1, prev[4]=2。
  • 起点是 prev 为 -1 的顶点：1 和 3。
  • 从1出发：1→2→4。从3出发：3（单点路径）。
  • 覆盖路径为：1→2→4 和 3。

算法复杂度

  • 二分图有 \(2n\) 个顶点，最多 \(m\) 条边。
  • 用 Hopcroft–Karp 算法求最大匹配的时间复杂度为 \(O(m\sqrt{n})\)。
  • 空间复杂度为 \(O(n+m)\)。

应用场景
该算法常用于任务调度、项目管理中，将任务（顶点）通过依赖关系（边）串成尽可能少的执行序列。

有向无环图（DAG）的最小路径覆盖（Min Path Cover in DAG）问题 问题描述 我们给定一个有向无环图（Directed Acyclic Graph, DAG），其顶点集为 \( V \)，边集为 \( E \)。 路径覆盖 是指图中一组 不相交 （即顶点不相交）的路径，使得图中 每一个顶点 都恰好出现在其中一条路径上。这里的“路径”可以是一个单顶点路径（即长度为0的路径）。 最小路径覆盖 是覆盖所有顶点所需 最少路径数量 的路径覆盖。 我们的目标：给定一个 DAG，求出其最小路径覆盖的具体方案（或至少求出最少路径数）。 解题思路 这是一个经典问题，可以用 二分图最大匹配 来高效求解。核心思想是： 将原 DAG 的每个顶点 \( v \) 拆成两个顶点：一个“出点”（在左部）、一个“入点”（在右部）。 原图中的每条有向边 \( u \to v \) 对应二分图中的一条从左部的 \( u_ {\text{out}} \) 到右部的 \( v_ {\text{in}} \) 的边。 在二分图中找到最大匹配，原图的最小路径覆盖数就等于顶点数减去最大匹配数。 最后通过匹配关系可以还原出具体的路径覆盖方案。 详细步骤 步骤1：构建二分图模型 设原 DAG 的顶点数为 \( n \)。构建二分图 \( B = (X, Y, E_ B) \)，其中： \( X = \{x_ 1, x_ 2, \dots, x_ n\} \) 对应原图每个顶点作为“路径起点”的可能性。 \( Y = \{y_ 1, y_ 2, \dots, y_ n\} \) 对应原图每个顶点作为“路径终点”的可能性。 对于原图的每条有向边 \( (u, v) \)，在二分图中添加一条从 \( x_ u \) 到 \( y_ v \) 的边。 直观理解 ：如果我们在二分图中选择边 \( (x_ u, y_ v) \)，意味着在原图中可以将顶点 \( u \) 和 \( v \) 连接在同一条路径上（即 \( v \) 是 \( u \) 的直接后继）。 步骤2：最大匹配与最小路径覆盖的关系 在二分图 \( B \) 中的一个匹配，表示我们选择了若干条原图中的“连接关系”，将不同顶点“串联”到同一条路径上。 关键性质：原图的一条路径覆盖对应二分图中的一个匹配，且路径数 = 顶点数 − 匹配边数。 原因：初始时，每个顶点自成一个单点路径，共 \( n \) 条路径。每当二分图中选中一条匹配边 \( (x_ u, y_ v) \)，我们就将 \( u \) 所在的路径和 \( v \) 所在的路径合并（即 \( v \) 所在的路径接到 \( u \) 所在路径的末尾），总路径数减少1。 为了最小化路径数，我们需要最大化匹配边数。因此： \[ \text{最小路径覆盖数} = n - \text{最大匹配数} \] 这里最大匹配是二分图 \( B \) 中的最大匹配。 步骤3：求解二分图最大匹配 二分图最大匹配可以用匈牙利算法（复杂度 \( O(nm) \)）或 Hopcroft–Karp 算法（复杂度 \( O(m\sqrt{n}) \)）求解。 我们用邻接表存储二分图 \( B \)，然后运行最大匹配算法即可得到最大匹配的边集。 步骤4：还原具体路径 设最大匹配结果为：对于某些顶点 \( u \) 和 \( v \)，匹配边为 \( (x_ u, y_ v) \)（表示 \( u \to v \) 的连接）。 我们需要从匹配关系还原出原图中的路径： 根据匹配边，构建一个数组 \( \text{next}[ u] \) 表示在原图中顶点 \( u \) 的下一个顶点是 \( v \)（如果 \( (x_ u, y_ v) \) 是匹配边），否则 \( \text{next}[ u ] = -1 \)。 同时，构建一个数组 \( \text{prev}[ v] \) 表示在原图中顶点 \( v \) 的前一个顶点是 \( u \)（如果 \( (x_ u, y_ v) \) 是匹配边），否则 \( \text{prev}[ v ] = -1 \)。 路径的起点是那些入度为0的顶点（在原图中没有前驱，即 \( \text{prev}[ u] = -1 \)）。从每个起点出发，沿着 \( \text{next} \) 数组走到终点（ \( \text{next}[ u ] = -1 \) 的顶点），即可得到一条路径。 所有顶点都会被覆盖，且这些路径两两不相交（因为匹配是顶点不相交的）。 举例说明 考虑一个 DAG 有顶点 {1,2,3,4} 和边：1→2, 1→3, 2→4, 3→4。 构建二分图： 左部 X = {x₁, x₂, x₃, x₄}，右部 Y = {y₁, y₂, y₃, y₄}。 边：x₁→y₂, x₁→y₃, x₂→y₄, x₃→y₄。 求最大匹配（用匈牙利算法）：一个最大匹配是 {(x₁, y₂), (x₂, y₄)} 或 {(x₁, y₃), (x₃, y₄)}，匹配数为2。 则最小路径覆盖数 = 4 − 2 = 2。 以匹配 {(x₁, y₂), (x₂, y₄)} 为例： next[ 1]=2, next[ 2]=4, prev[ 2]=1, prev[ 4 ]=2。 起点是 prev 为 -1 的顶点：1 和 3。 从1出发：1→2→4。从3出发：3（单点路径）。 覆盖路径为：1→2→4 和 3。 算法复杂度 二分图有 \( 2n \) 个顶点，最多 \( m \) 条边。 用 Hopcroft–Karp 算法求最大匹配的时间复杂度为 \( O(m\sqrt{n}) \)。 空间复杂度为 \( O(n+m) \)。 应用场景 该算法常用于任务调度、项目管理中，将任务（顶点）通过依赖关系（边）串成尽可能少的执行序列。