在最大流的 Push Relabel 算法中，为什么没有从源 s 到接收器 t 的路径？
我很难理解 CLRS 中的以下引理：
设 G 为流网络，s 和 t 为源节点和汇节点，f 为从 s 到 t 的预流，h 为 G 上的高度函数。则残差中不存在从 s 到 t 的增广路径图 Gf.
这是为什么呢？
I have difficulty understanding the following lemma from CLRS:
Let G be a flow network, s and t be source and sink nodes, f be a preflow from s to t, and h be a height function on G. Then there is no augmenting path from s to t in the residual graph Gf.
Why is this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
以下是 CLRS 第二版中证明的解释和扩展版本。
证明背后的直觉是，如果 h 是高度函数，那么我们必须在从 s 到 t 的任何路径中，沿路径的节点的高度在每一步中最多可以减少 1（因为高度函数满足属性 h(u) ≤ h(v) + 1，即 h(v) ≥ h(u) - 1)。现在假设残差图中有一条从 s 到 t 的增广路径。在这种情况下，如果存在增广路径，则必定存在从 s 到 t 的增广简单路径，因此我们无需担心环路。
那么让我们思考一下这条简单的路径是什么样子的。如果有|V|图中的顶点，我们的简单路径最多必须有 |V|其中最多有 |V| 个顶点，这意味着它最多有 |V| - 其中有 1 个边缘。因为最多有|V| - 1条边，每一步每个节点的高度最多可以下降1条，从起始节点s开始高度最大可能下降为|V| - 1. 现在，我们知道h是高度函数，这意味着h(s) = |V| h(t) = 0。但是现在我们有一个矛盾 - 因为我们从高度 |V| 开始并将高度最多减少 |V| - 1，路径末端的高度必须至少为 1，并且由于 h(t) = 0 我们知道这条路径实际上不能在 t 结束。这个矛盾保证了我们的假设是错误的，并且确实不存在从 s 到 t 的增广路径。
希望这有帮助！
The following is a paraphrased and expanded version of the proof in CLRS, Second Edition.
The intuition behind the proof is that if h is a height function, then we must have that in any path from s to t, the height of the nodes along the path can decrease by at most one in each step (since height functions satisfy the property that h(u) ≤ h(v) + 1, meaning that h(v) ≥ h(u) - 1). So now suppose that you have an augmenting path in the residual graph that goes from s to t. In that case, if there's an augmenting path, there must be an augmenting simple path from s to t, so we don't need to worry about cycles.
So let's think about what this simple path must look like. If there are |V| vertices in the graph, our simple path must have at most |V| vertices in it, which means that it has at most |V| - 1 edges in it. Because there are at most |V| - 1 edges, and the height of each node can drop by at most one per step, the maximum possible decrease in height from the starting node s is |V| - 1. Now, we know that h is a height function, which means that h(s) = |V| and h(t) = 0. But now we have a contradiction - since we start at height |V| and decrease the height by at most |V| - 1, the height at the end of the path has to be at least 1, and since h(t) = 0 we know that this path can't actually end at t. This contradiction guarantees that our assumption was wrong and that there really is no augmenting path from s to t.
Hope this helps!