我很难理解来自 CLRS 的以下引理：
设 G 是一个流网络，s 和 t 是源和汇节点，f 是从 s 到 t 的预流，h 是 G 上的高度函数。那么在残差图 G f中没有从 s 到 t 的增广路径.
为什么是这样？
user494461
问问题
332 次
1 回答
2
以下是 CLRS 第二版中证明的解释和扩展版本。
证明背后的直觉是，如果 h 是一个高度函数，那么我们必须有，在从 s 到 t 的任何路径中，沿路径的节点的高度在每一步中最多可以减少一个（因为高度函数满足h(u) ≤ h(v) + 1 的性质，即 h(v) ≥ h(u) - 1)。所以现在假设你在残差图中有一条从 s 到 t 的增广路径。在这种情况下，如果存在增广路径，那么从 s 到 t 一定存在增广简单路径，因此我们无需担心循环。
因此，让我们考虑一下这条简单的路径必须是什么样子。如果有 |V| 图中的顶点，我们的简单路径最多必须有 |V| 顶点，这意味着它最多有 |V| - 1 个边缘。因为最多有 |V| - 1 条边，每个节点的高度每步最多下降一个，从起始节点 s 开始的最大可能下降高度为 |V| - 1. 现在，我们知道 h 是一个高度函数，这意味着 h(s) = |V| 和 h(t) = 0。但现在我们有一个矛盾 - 因为我们从高度 |V| 开始 并将高度最多减少 |V| - 1，路径末端的高度必须至少为 1，并且由于 h(t) = 0，我们知道这条路径实际上不能在 t 处结束。这种矛盾保证了我们的假设是错误的，并且确实没有从 s 到 t 的增广路径。
希望这可以帮助！
于 2012-02-13T17:29:24.327 回答