有向无环图（DAG）的最小路径覆盖（不相交）问题
字数 2626 2025-12-23 11:38:30

有向无环图（DAG）的最小路径覆盖（不相交）问题

问题描述

给定一个有向无环图 \(G = (V, E)\)，我们需要找出一个最小的路径集合 \(P\)，使得：

  1. 每条路径是 \(G\) 中的一条有向路径（即顶点序列，满足相邻顶点间有边）。
  2. 这些路径覆盖 \(G\) 的所有顶点（即每个顶点恰好出现在一条路径中，路径之间互不相交）。

求这样的最小路径数 \(|P|\)。

问题背景与理解

  • 路径：在有向图中，一条路径是一系列顶点 \(v_1, v_2, \dots, v_k\)，且对于每个 \(i\)，都有边 \((v_i, v_{i+1}) \in E\)。
  • 路径覆盖：集合 \(P\) 中的路径覆盖了所有顶点，且顶点互不重复（路径之间不相交）。
  • 目标：找到覆盖所有顶点的最少不相交路径数。

例如，一个 DAG 可能是一个任务依赖图，每条路径代表可以顺序执行的任务链。最小路径覆盖问题可以转化为图匹配问题，并用二分图最大匹配求解。

核心思路（二分图建模）

我们构造一个二分图 \(B = (X, Y, E')\)：

  • 将原图 \(G\) 的每个顶点 \(v\) 拆成两个顶点：左部 \(v_x \in X\) 和右部 \(v_y \in Y\)。
  • 对于原图 \(G\) 中的每条有向边 \((u, v) \in E\)，在二分图 \(B\) 中加入边 \((u_x, v_y) \in E'\)。

关键性质：

  • 二分图 \(B\) 中的一个匹配 \(M\) 表示：如果边 \((u_x, v_y) \in M\)，则原图中顶点 \(u\) 和 \(v\) 在同一条路径中，且 \(u\) 直接指向 \(v\)。
  • 匹配中的边数等于路径中“连接”的数量。每个匹配边对应路径中两个连续顶点间的连接。
  • 路径的条数 = 顶点数 - 匹配边数。

推理：
初始时，每个顶点独自成一条路径（共 \(n\) 条路径）。每当我们在二分图中找到一个匹配边 \((u_x, v_y)\)，就意味着可以将 \(u\) 所在的路径和 \(v\) 所在的路径合并（通过边 \(u \to v\) 连接）。每合并一次，路径数减少 1。因此：

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

其中 \(n = |V|\)。

算法步骤

步骤 1：构造二分图

  • 输入 DAG \(G = (V, E)\)。
  • 创建二分图 \(B\)：左部 \(X = \{v_x \mid v \in V\}\)，右部 \(Y = \{v_y \mid v \in V\}\)。
  • 对于每条边 \((u, v) \in E\)，在 \(B\) 中加入边 \((u_x, v_y)\)。

步骤 2：计算二分图最大匹配

  • 使用匈牙利算法（\(O(n \cdot m)\)）或 Hopcroft–Karp 算法（\(O(m \sqrt{n})\)）求出二分图 \(B\) 的最大匹配 \(M\)。
  • 记匹配大小为 \(|M|\)。

步骤 3：计算最小路径数

  • 最小路径数 = \(n - |M|\)。

步骤 4（可选）：输出具体路径

  • 根据匹配 \(M\) 还原路径：
    1. 在匹配中，每条匹配边 \((u_x, v_y)\) 表示在原图中 \(u \to v\)。
    2. 从所有右部未匹配的顶点 \(v_y\) 出发（即路径的终点），沿着匹配边反向追踪，直到左部未匹配的顶点（路径的起点）。
    3. 每条追踪出的序列即为一条路径。

举例说明

考虑以下 DAG（顶点编号 1 到 4）：

  • 边：1→2, 1→3, 2→4, 3→4。

步骤 1：构造二分图

  • 左部：\(X = \{1_x, 2_x, 3_x, 4_x\}\)
  • 右部：\(Y = \{1_y, 2_y, 3_y, 4_y\}\)
  • 边：
    • 1→2 ⇒ (1_x, 2_y)
    • 1→3 ⇒ (1_x, 3_y)
    • 2→4 ⇒ (2_x, 4_y)
    • 3→4 ⇒ (3_x, 4_y)

步骤 2：求最大匹配

  • 一种最大匹配：\((1_x, 2_y), (2_x, 4_y)\)，大小 \(|M| = 2\)。
  • （也可匹配 (1_x,3_y) 和 (3_x,4_y)，结果相同）

步骤 3：最小路径数

  • \(n = 4\)，最小路径数 = \(4 - 2 = 2\)。

步骤 4：还原路径

  • 匹配边：(1_x,2_y) 表示 1→2；(2_x,4_y) 表示 2→4。
  • 右部未匹配顶点：3_y 和 1_y（注意右部未匹配的顶点对应原图中路径终点）。
  • 从 3_y 出发：在左部没有匹配到 3_y 的边，所以顶点 3 单独成路径：路径1 = [3]。
  • 从 1_y 出发：右部顶点 1_y 未匹配，说明顶点 1 是某条路径的终点？不对，这里需要修正：右部未匹配的顶点在原图中是路径的终点，因为没有人指向它（在匹配中没有边进入它）。左部未匹配的顶点是路径的起点。
  • 更简单的方法：从匹配边构建路径：
    • 由 (1_x,2_y) 和 (2_x,4_y) 可连成 1→2→4。
    • 剩下顶点 3 未被覆盖，单独成路径 [3]。
  • 最终两条路径：[1→2→4] 和 [3]。

复杂度分析

  • 构造二分图：\(O(n + m)\)。
  • 求二分图最大匹配：
    • 匈牙利算法：\(O(n \cdot m)\)。
    • Hopcroft–Karp 算法：\(O(m \sqrt{n})\)。
  • 总复杂度取决于匹配算法，一般用 Hopcroft–Karp 更优。

为什么必须是有向无环图？

  • 如果图中有环，直接应用上述建模会出问题：因为环可能导致匹配形成圈，在还原路径时无法得到简单路径（可能形成环状结构）。
  • 但可以推广到有环图的最小路径覆盖（不相交）问题，不过需要先缩点（将强连通分量缩成一点）转化为 DAG，再对 DAG 求解。

总结

  • 核心转化：DAG 的最小不相交路径覆盖问题 ⇨ 二分图最大匹配问题。
  • 公式：最小路径数 = 顶点数 − 最大匹配数。
  • 算法流程：拆点建二分图 → 求最大匹配 → 计算路径数（→ 还原路径）。
  • 应用：任务调度、程序控制流分析等场景中，用于找出最少的不重叠执行链。

这个解法巧妙地将路径覆盖问题转化为匹配问题，是图论中“匹配模型”的经典应用之一。

有向无环图（DAG）的最小路径覆盖（不相交）问题 问题描述 给定一个有向无环图 \(G = (V, E)\)，我们需要找出一个最小的路径集合 \(P\)，使得： 每条路径是 \(G\) 中的一条有向路径（即顶点序列，满足相邻顶点间有边）。 这些路径覆盖 \(G\) 的所有顶点（即每个顶点恰好出现在一条路径中，路径之间互不相交）。 求这样的最小路径数 \(|P|\)。 问题背景与理解 路径 ：在有向图中，一条路径是一系列顶点 \(v_ 1, v_ 2, \dots, v_ k\)，且对于每个 \(i\)，都有边 \((v_ i, v_ {i+1}) \in E\)。 路径覆盖 ：集合 \(P\) 中的路径覆盖了所有顶点，且顶点互不重复（路径之间不相交）。 目标 ：找到覆盖所有顶点的最少不相交路径数。 例如，一个 DAG 可能是一个任务依赖图，每条路径代表可以顺序执行的任务链。最小路径覆盖问题可以转化为图匹配问题，并用二分图最大匹配求解。 核心思路（二分图建模） 我们构造一个二分图 \(B = (X, Y, E')\)： 将原图 \(G\) 的每个顶点 \(v\) 拆成两个顶点：左部 \(v_ x \in X\) 和右部 \(v_ y \in Y\)。 对于原图 \(G\) 中的每条有向边 \((u, v) \in E\)，在二分图 \(B\) 中加入边 \((u_ x, v_ y) \in E'\)。 关键性质 ： 二分图 \(B\) 中的一个匹配 \(M\) 表示：如果边 \((u_ x, v_ y) \in M\)，则原图中顶点 \(u\) 和 \(v\) 在同一条路径中，且 \(u\) 直接指向 \(v\)。 匹配中的边数等于路径中“连接”的数量。每个匹配边对应路径中两个连续顶点间的连接。 路径的条数 = 顶点数 - 匹配边数。 推理 ： 初始时，每个顶点独自成一条路径（共 \(n\) 条路径）。每当我们在二分图中找到一个匹配边 \((u_ x, v_ y)\)，就意味着可以将 \(u\) 所在的路径和 \(v\) 所在的路径合并（通过边 \(u \to v\) 连接）。每合并一次，路径数减少 1。因此： \[ \text{最小路径数} = n - \text{最大匹配数} \] 其中 \(n = |V|\)。 算法步骤 步骤 1：构造二分图 输入 DAG \(G = (V, E)\)。 创建二分图 \(B\)：左部 \(X = \{v_ x \mid v \in V\}\)，右部 \(Y = \{v_ y \mid v \in V\}\)。 对于每条边 \((u, v) \in E\)，在 \(B\) 中加入边 \((u_ x, v_ y)\)。 步骤 2：计算二分图最大匹配 使用匈牙利算法（\(O(n \cdot m)\)）或 Hopcroft–Karp 算法（\(O(m \sqrt{n})\)）求出二分图 \(B\) 的最大匹配 \(M\)。 记匹配大小为 \(|M|\)。 步骤 3：计算最小路径数 最小路径数 = \(n - |M|\)。 步骤 4（可选）：输出具体路径 根据匹配 \(M\) 还原路径： 在匹配中，每条匹配边 \((u_ x, v_ y)\) 表示在原图中 \(u \to v\)。 从所有右部未匹配的顶点 \(v_ y\) 出发（即路径的终点），沿着匹配边反向追踪，直到左部未匹配的顶点（路径的起点）。 每条追踪出的序列即为一条路径。 举例说明 考虑以下 DAG（顶点编号 1 到 4）： 边：1→2, 1→3, 2→4, 3→4。 步骤 1：构造二分图 左部：\(X = \{1_ x, 2_ x, 3_ x, 4_ x\}\) 右部：\(Y = \{1_ y, 2_ y, 3_ y, 4_ y\}\) 边： 1→2 ⇒ (1_ x, 2_ y) 1→3 ⇒ (1_ x, 3_ y) 2→4 ⇒ (2_ x, 4_ y) 3→4 ⇒ (3_ x, 4_ y) 步骤 2：求最大匹配 一种最大匹配：\((1_ x, 2_ y), (2_ x, 4_ y)\)，大小 \(|M| = 2\)。 （也可匹配 (1_ x,3_ y) 和 (3_ x,4_ y)，结果相同） 步骤 3：最小路径数 \(n = 4\)，最小路径数 = \(4 - 2 = 2\)。 步骤 4：还原路径 匹配边：(1_ x,2_ y) 表示 1→2；(2_ x,4_ y) 表示 2→4。 右部未匹配顶点：3_ y 和 1_ y（注意右部未匹配的顶点对应原图中路径终点）。 从 3_ y 出发：在左部没有匹配到 3_ y 的边，所以顶点 3 单独成路径：路径1 = [ 3 ]。 从 1_ y 出发：右部顶点 1_ y 未匹配，说明顶点 1 是某条路径的终点？不对，这里需要修正：右部未匹配的顶点在原图中是路径的 终点 ，因为没有人指向它（在匹配中没有边进入它）。左部未匹配的顶点是路径的 起点 。 更简单的方法：从匹配边构建路径： 由 (1_ x,2_ y) 和 (2_ x,4_ y) 可连成 1→2→4。 剩下顶点 3 未被覆盖，单独成路径 [ 3 ]。 最终两条路径：[ 1→2→4] 和 [ 3 ]。 复杂度分析 构造二分图：\(O(n + m)\)。 求二分图最大匹配： 匈牙利算法：\(O(n \cdot m)\)。 Hopcroft–Karp 算法：\(O(m \sqrt{n})\)。 总复杂度取决于匹配算法，一般用 Hopcroft–Karp 更优。 为什么必须是有向无环图？ 如果图中有环，直接应用上述建模会出问题：因为环可能导致匹配形成圈，在还原路径时无法得到简单路径（可能形成环状结构）。 但可以推广到有环图的最小路径覆盖（不相交）问题，不过需要先缩点（将强连通分量缩成一点）转化为 DAG，再对 DAG 求解。 总结 核心转化 ：DAG 的最小不相交路径覆盖问题 ⇨ 二分图最大匹配问题。 公式 ：最小路径数 = 顶点数 − 最大匹配数。 算法流程 ：拆点建二分图 → 求最大匹配 → 计算路径数（→ 还原路径）。 应用 ：任务调度、程序控制流分析等场景中，用于找出最少的不重叠执行链。 这个解法巧妙地将路径覆盖问题转化为匹配问题，是图论中“匹配模型”的经典应用之一。