图论中的最小路径覆盖问题（二分图匹配应用） 问题描述 最小路径覆盖问题是指：给定一个有向无环图（DAG），要求用最少数量的不相交路径（即路径之间没有公共顶点）覆盖图中所有顶点。这里的"覆盖"意味着每个顶点恰好出现在一条路径中。 关键思路 这个问题的巧妙之处在于将其转化为二分图最大匹配问题： 将原DAG的每个顶点v拆分成两个顶点：左部顶点vₗ（代表作为路径起点）和右部顶点vᵣ（代表作为路径终点） 对于原图中的每条有向边(u→v)，在二分图中添加从左部uₗ到右部vᵣ的边 在二分图中求最大匹配，最小路径覆盖数 = 原图顶点数 - 最大匹配数 详细解题步骤 步骤1：理解问题转换的原理 在路径覆盖中，每个顶点有三种角色：路径起点、路径中间点、路径终点 路径起点的特征是：只有出边，没有入边（在当前路径中） 路径终点的特征是：只有入边，没有出边（在当前路径中） 中间点的特征是：既有入边又有出边 匹配边(uₗ→vᵣ)表示顶点u的后继是v，即u→v是路径中的一条边 步骤2：构建二分图模型 假设原DAG有n个顶点，编号为1,2,...,n： 创建左部顶点集：{1ₗ, 2ₗ, ..., nₗ} 创建右部顶点集：{1ᵣ, 2ᵣ, ..., nᵣ} 对于原图中每条边(u→v)，添加边(uₗ→vᵣ)到二分图 步骤3：二分图匹配算法应用 使用匈牙利算法求二分图的最大匹配M： 初始化匹配数组match，大小为n，初始值为-1 对每个左部顶点uₗ，尝试为其寻找匹配的右部顶点 使用DFS或BFS进行增广路径查找 步骤4：从匹配结果重构路径覆盖 在最大匹配M中，如果存在边(uₗ→vᵣ)，说明顶点u的后继是v 未被匹配的左部顶点对应路径起点 未被匹配的右部顶点对应路径终点 从每个起点开始，沿着匹配边遍历，即可得到各条路径 步骤5：数学原理证明 初始状态：每个顶点自成一条路径，共n条路径 每次匹配成功意味着两条路径可以合并（u所在的路径和v所在的路径连接） 最大匹配数k表示最多可以合并k次 因此最小路径覆盖数 = n - k 实例演示 考虑有向图：顶点{1,2,3,4}，边{1→2, 1→3, 2→4, 3→4} 构建二分图： 左部：{1ₗ,2ₗ,3ₗ,4ₗ}，右部：{1ᵣ,2ᵣ,3ᵣ,4ᵣ} 边集：{1ₗ→2ᵣ, 1ₗ→3ᵣ, 2ₗ→4ᵣ, 3ₗ→4ᵣ} 求最大匹配： 可能的最大匹配：{1ₗ→2ᵣ, 3ₗ→4ᵣ}（大小为2） 最小路径覆盖数 = 4 - 2 = 2 路径重构： 路径1：1→2→4（从1开始，1匹配2，2匹配4） 路径2：3→4（但4已被使用，实际应为3单独成路径） 正确路径：1→2→4 和 3 算法复杂度 二分图构建：O(n+m)，其中n为顶点数，m为边数 匈牙利算法：O(n×m)或O(n³) 总复杂度：在稀疏图中通常很高效 这种转换的优美之处在于将看似复杂的路径覆盖问题转化为经典的二分图匹配问题，体现了图论中问题转换的重要思想。