フローネットワーク

目次

インタラクティブ

増加道、残余辺、最小カット

増加自動リセット

フローネットワーク（流量 / 容量）

増加道最小カット流量

「増加」を押して最初の増加道を求めます。

最大フロー = 最小カット

ネットワークは制約の範囲でフローを運ぶ

フローネットワークは、異なる始点 $s$ と終点 $t$ を持つ有限有向グラフです。元の各辺 $e$ には有限かつ非負の容量 $c_e$ があります。実行可能なフローとは、各辺に量 $f_e$ を割り当てて

$$0\le f_e\le c_e$$

を満たし、$s,t$ 以外の各頂点で流入量と流出量を等しくするものです。フロー値 $|f|$ は $s$ から出る正味量であり、$t$ に入る正味量にも等しくなります。

端点が同じ辺であっても、それぞれ別の辺として扱います。これは平行辺だけでなく、逆方向の残余辺を扱う際にも重要です。特定の元の辺に属する逆方向残余辺は、反対向きの別の元の辺とは異なります。

残余辺で増やす・取り消す

フロー $f_e$ が流れる元の辺 $e=(u,v)$ から、順方向残余辺 $u\to v$ と逆方向残余辺 $v\to u$ が生じます。順方向の残余容量 $c_e-f_e$ は $e$ に追加で流せる量、逆方向の残余容量 $f_e$ はすでに流した量を取り消せる量です。正の残余容量を持つ辺だけを使えます。

増加路は残余ネットワーク内の $s$ から $t$ への路です。路上の残余容量の最小値を $\Delta$ とし、順方向残余辺に対応する元のフローを $\Delta$ 増やし、逆方向残余辺に対応するフローを $\Delta$ 減らします。ボトルネック分だけ変更するため容量制約は保たれます。路の内部頂点では流入と流出の変化が釣り合い、フロー保存則も崩れません。フロー値は $\Delta$ 増加します。

取り消しは単なる帳尻合わせではなく、より良い経路へ組み替えるために必要です。容量がすべて1の辺 $s\to a$、$a\to b$、$b\to t$、$s\to b$、$a\to t$ を考えます。まず $s\to a\to b\to t$ に1を流します。次の増加路は $s\to b$、$a\to b$ の逆方向残余辺 $b\to a$、そして $a\to t$ です。この路は先の $a\to b$ のフローを取り消して経路を組み替え、値2のフローを実現します。

カットがフローの上限を証明する

$s$–$t$ カットは、$s\in S$、$t\in T$ となるよう頂点を $S,T$ に分けたものです。カット容量では、元の辺のうち $S$ から $T$ へ向かう辺だけを数えます。

$$c(S,T)=\sum_{e=(u,v):u\in S,v\in T}c_e.$$

$S$ の正味流出量を合計すると内部辺が相殺され、

$$|f|=\sum_{S\to T}f_e-\sum_{T\to S}f_e\le c(S,T)$$

となります。したがって、すべての実行可能なフローはすべてのカット容量以下です。上の単位容量の例では、$S=\{s\}$ のカット容量は2で、組み替えたフロー値も2なので最適性が証明できます。一般に増加路がなくなったとき、$s$ から残余グラフで到達可能な頂点がカットを定めます。外向きの元の辺は飽和し、逆向きの辺にはフローがないため、カット容量は現在のフロー値と等しくなります。ゆえにそのフローは最大です。

増加はいつ停止するか

増加路が存在しないことは最大性を特徴づけますが、容量の種類を問わず、どの経路選択でも有限回でその状態に達するという保証ではありません。ゼロフローから始め、容量が整数なら、フォード・ファルカーソン法は整数フローを保ちます。整数であるフロー値は毎回少なくとも1増え、始点から出る総容量が有限な上限なので、処理は停止します。有理数容量も共通分母を掛けて整数にすれば同じ保証があります。一方、任意の実数容量では、経路選択によって有限回で最大値に達せず、増加が無限に続くことがあります。

要点： 順方向残余辺はフローを増やし、逆方向残余辺は組み替えを可能にします。カットはこれ以上大きなフローがないことを示す証明書です。