我正在阅读 Cormen 等人的算法简介中的推流算法。
我很难理解引理 26.20，如下所述：
令 G = (V, E) 为源 s 和汇 t 的流网络，设 f 为 G 中的预流。那么，对于任何溢出的顶点 u，在残差网络 Gf 中存在从 u 到 s 的简单路径.
要查看此 leema 的上下文，可以在以下链接中找到。
http://integrator-crimea.com/ddu0164.html
请求您的帮助以了解这一点。
感谢您的时间和帮助。
问问题
372 次
1 回答
0
自从我查看所有这些最大流量的东西以来已经有一段时间了，但是如果我正确地考虑了这一点，这就是引理 26.20 所说的。
显然有一条从 s -> u 的路径，因为 u 中有多余的。要考虑的引理的重要部分是它指出有一条从 u -> s 的简单路径，它与导致 u 溢出的原始流的方向相反（因为流起源于 s 并流向 u）。由于 u 中存在溢出，因此存在一条从 s -> u 的简单路径，在整个路径中至少有 1 个单位的流量。即使 c(a,b) = 1 和 f(a,b) = 1 这使得 c(a,b) = 0 其中 a 和 b 都是该简单路径中的顶点对，那么 c(b,a) = c(b,a) - f(b,a) = 1 - (-1) = 2 因为 f(a,b) = -f(b,a)。因此，您可以在达到该方向的容量之前将 2 个单位推回该边缘（1 以抵消已经流动的 1 使流过该边缘 0，另一个使流过该边缘 1）。
您知道它是一条简单路径的原因是因为如果没有从 s -> u 的简单路径，则根本不会有流过 u。这是因为即使有从 s 到达 u 的非简单方法，也必须至少有一种简单的方法，否则所有流将被捕获在非简单路径中，这意味着没有人会通过 u。
想象一下。绘制一个流程图，其中源完全循环通过几个节点。是否可以在不创建返回 s 的简单剩余路径的情况下点击 u（选择一个节点）？现在尝试制作一个在几个边都指向 u 的最大流量。现在尝试找到返回 s 的简单路径。这可以证明引理 26.20 在说什么。其中一些引理很难理解，但一旦你真正考虑它，它通常就会有意义。他们只是通过反证法来证明这一点，这是正式证明他们所说的话的最佳方式。另外，请查看有关此的 wiki 页面，它与往常一样有一些很好的见解！http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm
希望这是有道理的，如果它不只是让我知道，我愿意与您合作！
于 2012-07-11T18:32:37.320 回答