DAG 上的最大不相交路径覆盖问题（Maximum Disjoint Path Cover in DAG）
字数 1974 2025-12-24 07:19:04

DAG 上的最大不相交路径覆盖问题（Maximum Disjoint Path Cover in DAG）

题目描述
给定一个有向无环图（DAG）\(G = (V, E)\)，我们称一条路径是“简单路径”，即顶点不重复。目标是用最少数量顶点不相交的简单路径覆盖图中的所有顶点（即每个顶点恰好出现在一条路径中）。注意，这里的“路径”是 DAG 上的一条有向路径，且路径之间不允许有公共顶点（顶点不相交）。
问题：求最少需要多少条这样的路径才能覆盖所有顶点，并输出一种覆盖方案。

背景
该问题是图论中路径覆盖问题的典型形式，常用在调度、序列分析、任务链规划等领域。其核心思想是通过图论建模，转化为经典的最大匹配问题来解决。

关键思路
将原 DAG 中的每个顶点 \(v\) 拆分成两个顶点：左部顶点 \(v_{out}\)（代表 v 作为路径的起点或中间点的前驱），右部顶点 \(v_{in}\)（代表 v 作为路径的终点或中间点的后继）。然后根据原图的有向边建立从左部到右部的边，形成二分图。在该二分图上求最大匹配，即可得到原问题的最优解。

拆分理由
对于任意一条路径 \(v_1 \to v_2 \to \dots \to v_k\)，除了路径的起点 \(v_1\) 没有被前驱覆盖，终点 \(v_k\) 没有被后继覆盖，中间的每个顶点 \(v_i\)（\(1 < i < k\)）都有一个前驱和一个后继。如果我们用匹配边 \((v_{out}, u_{in})\) 表示原图中存在边 \(v \to u\) 并且 u 在路径中紧接在 v 之后，那么每条路径对应匹配中的一组链。路径条数 = 总顶点数 - 匹配边数。

具体步骤

  1. 构建二分图

    • 对于 DAG \(G=(V,E)\)，创建二分图 \(B=(U,W,M)\)，其中 \(U = \{u_1, u_2, \dots, u_n\}\) 对应原图的 n 个顶点作为“出点”，\(W = \{w_1, w_2, \dots, w_n\}\) 对应原图的 n 个顶点作为“入点”。
    • 对于原图中每条有向边 \((x, y) \in E\)，在二分图中加入边 \((u_x, w_y)\)（即 x 的出点连到 y 的入点）。
    • 注意：二分图中的点数是 2n，边数是 m（与原图相同）。

  2. 求最大匹配

    • 在二分图 B 上使用匈牙利算法（若 n 较小）或 Hopcroft–Karp 算法（n 较大）求出最大匹配 M。
    • 设匹配大小为 |M|。

  3. 计算最小路径覆盖数

    • 结论：最小路径覆盖数（顶点不相交） = n - |M|。
    • 理由：每个匹配边对应原图中一条有向边的“连接”，匹配边数每增加 1，就可以将两条路径合并（或将一条路径延长），从而减少一条路径。初始时每个顶点单独为一条路径（共 n 条），每有一个匹配就减少一条路径。

  4. 还原路径方案

    • 根据匹配 M，构造一个有向图 \(G'\)：顶点为原图顶点，对于匹配边 \((u_x, w_y)\)，在 G' 中加入有向边 \(x \to y\)。
    • 此时 G' 是若干条不相交链的集合（因为每个顶点在匹配中最多有一条出边和一条入边，且无环）。
    • 找出所有链的起点（即入度为 0 的顶点），沿出边遍历即可得到各条路径。

举例说明
设 DAG 有 4 个顶点：\(V=\{1,2,3,4\}\)，边：\(1\to2, 1\to3, 2\to4, 3\to4\)。

  1. 拆点：左部 \(\{1_o,2_o,3_o,4_o\}\)，右部 \(\{1_i,2_i,3_i,4_i\}\)。
  2. 加边：\(1_o\to2_i, 1_o\to3_i, 2_o\to4_i, 3_o\to4_i\)。
  3. 二分图最大匹配：例如匹配 \(\{1_o-2_i, 3_o-4_i\}\)，大小 |M|=2。
  4. 最小路径覆盖数 = 4 - 2 = 2。
  5. 还原：匹配边对应原边 \(1\to2, 3\to4\)，加上未匹配的顶点（这里没有未被覆盖的顶点），得到两条路径：\(1\to2\) 和 \(3\to4\)。检查覆盖了所有顶点。

算法复杂度

  • 拆点与建图：O(n+m)
  • 求二分图最大匹配：使用 Hopcroft–Karp 算法为 O(m√n)，匈牙利算法为 O(nm)
  • 还原路径：O(n+m)
    总复杂度通常由匹配算法决定。

总结
DAG 上的最大不相交路径覆盖问题通过拆点转化为二分图最大匹配，利用 König 定理的推广形式得到最优解。这种方法高效且易于实现，是图论中“匹配建模”的经典应用之一。

DAG 上的最大不相交路径覆盖问题（Maximum Disjoint Path Cover in DAG） 题目描述 给定一个有向无环图（DAG）\( G = (V, E) \)，我们称一条路径是“简单路径”，即顶点不重复。目标是用最少数量 顶点不相交 的简单路径覆盖图中的所有顶点（即每个顶点恰好出现在一条路径中）。注意，这里的“路径”是 DAG 上的一条有向路径，且路径之间不允许有公共顶点（顶点不相交）。 问题：求最少需要多少条这样的路径才能覆盖所有顶点，并输出一种覆盖方案。 背景 该问题是图论中路径覆盖问题的典型形式，常用在调度、序列分析、任务链规划等领域。其核心思想是通过图论建模，转化为经典的最大匹配问题来解决。 关键思路 将原 DAG 中的每个顶点 \( v \) 拆分成两个顶点：左部顶点 \( v_ {out} \)（代表 v 作为路径的起点或中间点的前驱），右部顶点 \( v_ {in} \)（代表 v 作为路径的终点或中间点的后继）。然后根据原图的有向边建立从左部到右部的边，形成二分图。在该二分图上求最大匹配，即可得到原问题的最优解。 拆分理由 对于任意一条路径 \( v_ 1 \to v_ 2 \to \dots \to v_ k \)，除了路径的起点 \( v_ 1 \) 没有被前驱覆盖，终点 \( v_ k \) 没有被后继覆盖，中间的每个顶点 \( v_ i \)（\( 1 < i < k \)）都有一个前驱和一个后继。如果我们用匹配边 \( (v_ {out}, u_ {in}) \) 表示原图中存在边 \( v \to u \) 并且 u 在路径中紧接在 v 之后，那么每条路径对应匹配中的一组链。路径条数 = 总顶点数 - 匹配边数。 具体步骤 构建二分图 对于 DAG \( G=(V,E) \)，创建二分图 \( B=(U,W,M) \)，其中 \( U = \{u_ 1, u_ 2, \dots, u_ n\} \) 对应原图的 n 个顶点作为“出点”，\( W = \{w_ 1, w_ 2, \dots, w_ n\} \) 对应原图的 n 个顶点作为“入点”。 对于原图中每条有向边 \( (x, y) \in E \)，在二分图中加入边 \( (u_ x, w_ y) \)（即 x 的出点连到 y 的入点）。 注意：二分图中的点数是 2n，边数是 m（与原图相同）。 求最大匹配 在二分图 B 上使用匈牙利算法（若 n 较小）或 Hopcroft–Karp 算法（n 较大）求出最大匹配 M。 设匹配大小为 |M|。 计算最小路径覆盖数 结论：最小路径覆盖数（顶点不相交） = n - |M|。 理由：每个匹配边对应原图中一条有向边的“连接”，匹配边数每增加 1，就可以将两条路径合并（或将一条路径延长），从而减少一条路径。初始时每个顶点单独为一条路径（共 n 条），每有一个匹配就减少一条路径。 还原路径方案 根据匹配 M，构造一个有向图 \( G' \)：顶点为原图顶点，对于匹配边 \( (u_ x, w_ y) \)，在 G' 中加入有向边 \( x \to y \)。 此时 G' 是若干条不相交链的集合（因为每个顶点在匹配中最多有一条出边和一条入边，且无环）。 找出所有链的起点（即入度为 0 的顶点），沿出边遍历即可得到各条路径。 举例说明 设 DAG 有 4 个顶点：\( V=\{1,2,3,4\} \)，边：\( 1\to2, 1\to3, 2\to4, 3\to4 \)。 拆点：左部 \( \{1_ o,2_ o,3_ o,4_ o\} \)，右部 \( \{1_ i,2_ i,3_ i,4_ i\} \)。 加边：\( 1_ o\to2_ i, 1_ o\to3_ i, 2_ o\to4_ i, 3_ o\to4_ i \)。 二分图最大匹配：例如匹配 \( \{1_ o-2_ i, 3_ o-4_ i\} \)，大小 |M|=2。 最小路径覆盖数 = 4 - 2 = 2。 还原：匹配边对应原边 \( 1\to2, 3\to4 \)，加上未匹配的顶点（这里没有未被覆盖的顶点），得到两条路径：\( 1\to2 \) 和 \( 3\to4 \)。检查覆盖了所有顶点。 算法复杂度 拆点与建图：O(n+m) 求二分图最大匹配：使用 Hopcroft–Karp 算法为 O(m√n)，匈牙利算法为 O(nm) 还原路径：O(n+m) 总复杂度通常由匹配算法决定。 总结 DAG 上的最大不相交路径覆盖问题通过拆点转化为二分图最大匹配，利用 König 定理的推广形式得到最优解。这种方法高效且易于实现，是图论中“匹配建模”的经典应用之一。