文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文基于本仓库 docs/Chap26/Problems/26-2.md 的完整解答深入讲解《算法导论第三版》第 26 章问题 26-2「最小路径覆盖」如何把一个有向无环图DAG的最小路径覆盖问题通过「顶点拆分 单位容量」的归约转化为最大流问题用任意最大流算法求解并严格论证其正确性、给出 $O(VE)$ 的运行时间上界。读者学完后将掌握一类「把组合优化问题编码进流网络」的经典建模手法并理解为什么同样的构造在含环有向图上会失效——本文用教科书反例完整解释失效机理。1. 问题定义路径覆盖与最小路径覆盖设 $G (V, E)$ 是一个有向图路径覆盖path cover一组两两顶点不相交vertex-disjoint的路径集合 $P$使得 $V$ 中每个顶点恰好出现在 $P$ 中的一条路径上。路径的起点和终点可以是任意顶点长度任意包括长度为 0 的单点路径。最小路径覆盖minimum path cover包含路径条数最少的路径覆盖。对 $n$ 个顶点的任意路径覆盖存在一个关键恒等式若覆盖包含 $k$ 条路径则这 $k$ 条路径总共使用 $n - k$ 条边。这个恒等式是整个正确性证明的核心杠杆——它把「路径数最少」等价地翻译成「覆盖边数最多」而后者恰好可以编码成流的大小。2. 核心构造把路径覆盖编码为流网络 $G$本题给出一个经典归约手法对顶点进行「出副本 / 入副本」拆分把原图每条边 $(i, j)$ 编码为从「出副本」到「入副本」的一条单位容量边再引入超级源点与超级汇点。假设顶点集合 $V {1, 2, \ldots, n}$构造新图 $G (V, E)$$$ \begin{aligned} V {x_0, x_1, \ldots, x_n} \cup {y_0, y_1, \ldots, y_n}, \\ E {(x_0, x_i): i \in V} \cup {(y_i, y_0): i \in V} \cup {(x_i, y_j): (i, j) \in E}, \end{aligned} $$其中 $x_0$ 充当源点 $s$$y_0$ 充当汇点 $t$。三条边族的角色分别是边族含义作用$(x_0, x_i)$$i \in V$源点到每个顶点的「出副本」保证每个顶点至多作为一条路径的起点单位容量$(y_i, y_0)$$i \in V$每个顶点的「入副本」到汇点保证每个顶点至多作为一条路径的终点单位容量$(x_i, y_j)$$(i, j) \in E$原图边的「出 → 入」编码表示路径覆盖中选用原图边 $(i, j)$给 $G$ 中每条边赋容量 1然后运行任意最大流算法。2.1 从最大流恢复路径覆盖解答给出的恢复规则是若最大流中边 $(x_i, y_j)$ 的流量为 1则在路径覆盖中放入原图边 $(i, j)$。由此得到的边集再与「孤立」顶点合并即构成原图的一个路径覆盖。从直观上看一条从 $s x_0$ 到 $t y_0$ 的单位流路径$$ x_0 \to x_{i_1} \to y_{i_2} \to x_{i_2} \to y_{i_3} \to \cdots \to y_{i_k} \to y_0 $$对应原图中的一条顶点序列 $i_1, i_2, \ldots, i_k$其中相邻顶点之间恰好是原图边 $(i_1, i_2), (i_2, i_3), \ldots$。由于所有容量均为 1 且流守恒每条这样的单位流路径对应原图一条真正的路径且不同流路径的顶点互不相交——这正是路径覆盖的定义。需要说明的是原图 $G$ 是无环的 DAG因此上述序列中的顶点不可能重复否则就构成环恢复结果天然是合法的路径集合。这也是第 4 节中该算法只适用于 DAG 的关键。3. 正确性证明为什么「最大流 ⇒ 最小路径覆盖」解答对该归约给出三部分论证路径合法性 → 覆盖完整性 → 最优性。拆解为三条引理逐条说明。3.1 引理 1恢复出的边集不会产生重复顶点的「路径」没有顶点会在同一条路径中出现两次。反设存在 $f(x_i, y_j) f(x_k, y_j)$ 且 $i \ne k$即两个不同的「出副本」同时把流量送进同一个「入副本」 $y_j$。此时 $y_j$ 的流入为 2但其唯一出边 $(y_j, y_0)$ 容量仅为 1——违背流守恒flow conservation矛盾。因此每个 $y_j$ 至多接收一个单位流入对应原图中每个顶点 $j$ 至多被一条路径的边「进入」。每个顶点至多作为一条路径的起点。由于 $s x_0$ 到每个 $x_i$ 的边容量为 1流守恒保证不可能同时出现 $(x_i, y_j)$ 与 $(x_i, y_k)$$k \ne j$两条流量为 1 的边——否则 $x_i$ 的流出量会超过其唯一入边 $(x_0, x_i)$ 的容量。因此原图中每个顶点 $i$ 至多被一条路径的边「离开」。综合起来恢复出的边集在任意顶点上的入度、出度至多为 1只可能构成若干条简单路径在 DAG 上不可能构成环即每个顶点被至多一条路径覆盖。3.2 引理 2覆盖是完整的——每个顶点都在某条路径上对任意顶点 $j$若既没有边 $(x_i, y_j)$ 也没有边 $(x_j, y_i)$ 被选中即 $j$ 既不是任何选中边的终点也不是起点那么 $j$单独构成一条长度为 0 的路径路径覆盖允许长度为 0 的单点路径。于是每个顶点必然被纳入覆盖不存在「漏掉」的顶点。3.3 引理 3最优性——最大流必然给出最小覆盖由第 1 节的恒等式$n$ 个顶点的覆盖若有 $k$ 条路径则覆盖边数为 $n - k$。反过来给定任意路径覆盖可以恢复出一个流当且仅当 $(i, j)$ 是覆盖中某条路径的边时令 $f(x_i, y_j) 1$。这个流满足容量约束与流守恒流量恰为 $n - k$$s$ 出发的总流量。用反证法证明最优性。设最大流算法恢复出的覆盖有 $k$ 条路径对应流量 $n - k$若真正的最小路径覆盖使用的路径数严格少于 $k$那么它使用的边数严格多于 $n - k$于是按上述规则可以恢复出一个流量严格大于 $n - k$的合法流——这与「$n - k$ 是最大流值」矛盾。因此最大流恢复出的覆盖必然是最小路径覆盖。3.4 复杂度最大流 ⇔ 最大二分匹配$O(VE)$解答指出一个深层联系$G$ 中的最大流等价于在只保留 $x_1,\ldots,x_n$ 与 $y_1,\ldots,y_n$ 两部分、边集为 ${(x_i, y_j): (i,j)\in E}$ 的二分图bipartite graph上求最大匹配maximum matching。原因在于源边 $(x_0, x_i)$、汇边 $(y_i, y_0)$ 与中间边 $(x_i, y_j)$ 均为单位容量由整数性定理integrality theorem见 docs/Chap26/26.2.md 的 26.2-2/26.2-3 与 docs/Chap26/26.3.md 中的 Theorem 26.10单位容量网络上最大流是整数的每条中间边流量非 0 即 1流量为 1 的中间边 $(x_i, y_j)$ 恰好构成二分图的一组匹配边最大流值等于最大匹配的基数Corollary 26.11。根据 docs/Chap26/26.3.md26.3 节「最大二分匹配」的结论在单位容量二分匹配流网络上运行最大流算法每次增广将流量提升 1最多增广 $O(V)$ 次故总运行时间为 $O(VE)$。由此得到最小路径覆盖规模公式$$ \text{最小路径数} n - \text{最大匹配基数} n - |f_{\max}|. $$3.5 恢复路径覆盖的实操步骤完整算法流程构造 $G$顶点 $x_0, x_1, \ldots, x_n$ 与 $y_0, y_1, \ldots, y_n$按第 2 节三条边族建边容量全部为 1运行任意最大流算法Ford-Fulkerson / Edmonds-Karp / Dinic 均可单位容量下任选对每条流量为 1 的中间边 $(x_i, y_j)$输出原图边 $(i, j)$从这些边组装路径任意未作为「后继」的顶点为路径起点沿选中的边顺次前进直到无后继既无前驱也无后继的顶点输出为单点路径统计路径条数 $k n - |f_{\max}|$即为最小路径覆盖的规模。4. 算法对含环有向图失效教科书反例剖析问题 b 问该算法对含有环的有向图是否仍然有效答案是否定的。解答给出了一个四顶点反例逐层剖析其失效机理。反例顶点集 ${1, 2, 3, 4}$边集 $(1, 2)$、$(2, 3)$、$(3, 1)$、$(4, 3)$。顶点 1、2、3 构成有向环顶点 4 有一条边进入该环。这个图的最小路径覆盖期望结果是单条路径$4 \to 3 \to 1 \to 2$——它恰好把全部 4 个顶点串成一条长度为 3 的路径对应流量 $n - k 4 - 1 3$。然而存在一个极大maximal但错误的流令 $(x_1, y_2)$、$(x_2, y_3)$、$(x_3, y_1)$ 三条边流量均为 1其余中间边流量为 0。这个流的值为 3$s x_0$ 发出三股单位流且残存网络中不存在从 $x_0$ 到 $y_0$ 的增广路$y_1, y_2, y_3$ 的汇边 $(y_i, y_0)$ 已全部饱和从 $x_4$ 出发可走到 $y_3$但 $y_3$ 已饱和、只能沿反向边退回 $x_2$而 $x_2$ 的所有可行出边均已饱和路径中断同理沿任何反向边进入 $x_1, x_2, x_3$ 后都无法再前进。因此该流是极大流事实上其值 3 也确实是最大值因为汇边容量之和为 3。但按第 2 节的恢复规则它选出的原图边为 $(1, 2)$、$(2, 3)$、$(3, 1)$——这构成一个有向环 $1 \to 2 \to 3 \to 1$而不是一条路径顶点 4 被孤立。这个「覆盖」里出现了环既不满足路径的定义路径不允许重复访问顶点也对应不上期望的单路径解。失效的本质正确性证明依赖 DAG 性质回到第 3 节引理 1恢复出的边集在每点上入度、出度至多为 1只能说明它是「若干条简单路径或环」的并集。在 DAG 中不可能出现环于是结论自动收敛为「若干条简单路径」而一旦原图含环最大流完全可以选中环上的边把「路径覆盖」破坏成「路径 环」的混合结构。这正是解答证明链条上「无环」这一前提所起的作用——去掉它引理 1 的结论从「路径」退化为「路径或环」整个归约随即崩溃。注意反例中两种配置的流量值同为 3表面上看「路径数 $n - $ 流量」的计数没有变化但计数正确不代表结构有效环不是路径恢复结果无法作为合法路径覆盖使用。因此该归约方法不能直接推广到一般含环有向图对一般有向图的最小路径覆盖需要其他建模方案超出本题范围。5. 归约手法的扩展视角与同章其他问题的呼应「单位容量 顶点拆分 / 二分图匹配」的建模手法在第 26 章中反复出现可横向对照docs/Chap26/26.3.md最大二分匹配的标准流网络构造源 → $L$、$L \to R$、$R \to$ 汇均为单位容量以及 Hall 定理26.3-4与 $d$-正则二分图26.3-5的流证明是本题复杂度论证的直接依据docs/Chap26/26.2.mdFord-Fulkerson 方法及其整数性Theorem 26.10、增广路分析是「单位容量 ⇒ 整数流 ⇒ 匹配」成立的底层原因docs/Chap26/Problems/26-1.md「逃生问题」escape problem同样用单位容量流网络刻画顶点不相交路径与路径覆盖在「用流表示不共享顶点的路径集合」这一点上同构docs/Chap26/Problems/26-6.mdHopcroft-Karp 算法把二分图最大匹配加速到 $O(\sqrt V, E)$若追求更优常数可在本题的匹配子问题上直接套用本题解答采用的仍是 26.3 节的 $O(VE)$ 结论。6. 小结问题 26-2 是「把组合问题归约为最大流」的经典示范要点可概括为建模顶点拆分为「出副本 $x_i$」与「入副本 $y_i$」用单位容量边编码原图边超级源汇 $(x_0, y_0)$ 负责起终点配额对应最大流值 $|f_{\max}|$ 对应路径覆盖的最大边数最小路径数 $n - |f_{\max}|$正确性三条引理分别保证「路径合法」「覆盖完整」「结果最优」其中「无环」是路径合法性成立的前提复杂度等价于二分图最大匹配运行时间 $O(VE)$边界原图含环时算法失效教科书反例环 $1 \to 2 \to 3 \to 1$ 加边 $(4, 3)$展示了极大流选中环边、导致恢复结果不再是路径覆盖的过程。完整原始解答见 docs/Chap26/Problems/26-2.md全仓库解决方案由 MkDocs KaTeX 渲染见 mkdocs.yml 中 nav 第 26 章配置与 README.md可在线阅读对照。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 第 24.2 节精讲DAG 中的单源最短路径DAG-SHORTEST-PATHS习题全解析CLRS 第 24.2 节精讲DAG 中的单源最短路径DAG SHORTEST PATHS习题全解析 导读本文基于仓库 docs/Chap24/24.2文档教程教育CLRS 问题 26-1 详解将网格逃逸问题Escape Problem归约为最大流问题CLRS 问题 26 1 详解将网格逃逸问题Escape Problem归约为最大流问题 导读 本文基于 docs/Chap26/Problems/26文档教程教育CLRS 26.2 习题精讲Ford-Fulkerson 方法、增广路径与最大流最小割的完整推演CLRS 26.2 习题精讲Ford Fulkerson 方法、增广路径与最大流最小割的完整推演 本节围绕《算法导论第三版》第 26 章 26.2 节T文档教程教育上一篇惠普OMEN游戏本终极性能优化OmenSuperHub完整使用指南下一篇绝区零一条龙「影像店营业」全自动经营RandomPlay 屏幕识别与状态机流程解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考