CLRS から次の補題を理解するのが困難です。
G をフロー ネットワーク、s と t をソース ノードとシンク ノード、f を s から t へのプリフロー、h を G の高さ関数とします。この場合、残差グラフ G fには s から t への拡張パスはありません。 .
どうしてこれなの？
user494461
質問する
332 次
1 に答える
2
以下は、CLRS 第 2 版の証明を言い換えて拡張したものです。
証明の背後にある直感は、h が高さ関数である場合、s から t への任意のパスで、パスに沿ったノードの高さは各ステップで最大 1 だけ減少できることを持たなければならないということです (高さ関数はh(u) ≤ h(v) + 1、つまり h(v) ≥ h(u) - 1 というプロパティ)。ここで、残差グラフに s から t に向かう拡張パスがあるとします。その場合、増補路があれば、s から t への増補単純路がなければならないので、循環について心配する必要はありません。
それでは、この単純なパスがどのように見えるべきかを考えてみましょう。|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 への増補パスが実際に存在しないことを保証します。
お役に立てれば！
于 2012-02-13T17:29:24.327 に答える