algorithm - push relabel算法分析

Question

我正在阅读 Cormen 等人的 Introduction to Algorithms 中的推流算法。

我在理解下面提到的引理 26.20 时遇到困难:

Let G = (V, E) be a flow network with source s and sink t, and let f be a preflow in G. Then, for any overflowing vertex u, there is a simple path from u to s in the residual network Gf.

要查看此 leema 的上下文，可以在以下链接中找到。

http://integrator-crimea.com/ddu0164.html

请您帮助理解这一点。

感谢您的宝贵时间和帮助。

Answer 1

自从我查看所有这些最大流量内容以来已经有一段时间了，但如果我正确地考虑了这一点，那么这就是引理 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(选择一个节点)？现在尝试制作一个流量在多个边上达到最大的流量，所有边都指向你。现在尝试找到一条返回 s 的简单路径。这可以证明引理 26.20 在说什么。其中一些引理很难理解，但一旦你真正思考它，它通常就会变得有意义。他们只是通过反证法来证明这一点，这是正式证明他们所说内容的最佳方式。另外，请查看关于此的 wiki 页面，它一如既往地有一些很好的见解! http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm

希望这是有道理的，如果它不只是让我知道，我愿意与您合作!