V wrt の頂点の有効なラベル付け。プリフロー x は関数 d[.] : V -> Z を満たす:
d[s] = n ^ d[t] = 0
すべての (v,w) は E に属します: d[v] <= d[w] + 1
(s と t) を含む 4 つの頂点があるとします。
d[s] = 4
有効なラベル付けによれば、d[v] <= d[w]+1 である必要がありますが、「s」に由来するエッジの場合、4 <= 1 は false であるため有効ではありません。このロジックはソースだけではありませんか？
私はそれを正しく理解していますか？私を修正してください。
お時間をいただきありがとうございます。
有効なラベル付けの定義は近いですが、正確ではありません。
E に属するすべての (v,w) に対して d[v] <= d[w] + 1 であると主張します。
ただし、これは実際には、R に属するすべての (v,w) に対して真である必要があるだけです。ここで、R は残差エッジです。
残留エッジは、電流フローがエッジの容量よりも少ないエッジです。
topcoderに適切な説明があります。
次の図を検討してください。
エッジのラベル (2/3 など) では、最初の数字は現在の流れを示し、2 番目の数字はエッジの容量を示します。
ノード上の数字は、各ノードの高さ関数 d を示します。
緑色のエッジは、予備の容量があるため、残りのエッジです。
したがって、高さの制約を確認するには、S->A エッジと B->T エッジを確認するだけで済みます。