algorithm - 最大フローアルゴリズムでの超過フローとオーバーフローの計算

Question

次のリンクでプッシュフローアルゴリズムを読んでいます。

http://community.topcoder.com/tc?module=静的&d1=チュートリアル&d2=maxflowPushRelabel

超過フロー - 超過フロー e を e(u) = f(V,u)、u への正味フローと定義します。e(u) > 0 の場合、頂点 u ∊ V-{s,t} はオーバーフロー/アクティブです。

単純なフローネットワークの例を探しています e(u) をどのように計算しますか?

お時間をいただきありがとうございます。

Answer 1

以下の図には、ソース ノード (S)、シンク ノード (T)、および内部ノード (A) があります。

数値は流れを示します (1 秒あたりのリットルなど)。A には 1 秒あたり 3 リットルが入りますが、A からは 1 秒あたり 1 リットルしか流れないので、A の超過流量は 2 です。

ノート

1. push-relabel アルゴリズムでは、内部ノードの超過フローを負にすることはできません。言い換えれば、入るよりも出るフローを多くすることはできません。

2. ソース ノードはフローを生成できます (内部ノードとしてカウントされないため、注 1 は適用されません)。

3. アルゴリズム中、最終的にすべての頂点の過剰フローが 0 になるまで、過剰フローが削減されます。

4. すべての着信フローを合計し、すべての発信フローを差し引くことで、超過フローを計算できます。

5. ただし、実際には、アルゴリズムは超過フローの配列を維持し、アルゴリズムの進行に応じて値を更新します。