問題定義

各エッジに対し、流量の最大値(容量、キャパシティ)が定められたグラフにおいて、単一の始点から単一の終点への流量の最大値(最大フロー)を求める。

解法

基本的な考え方

  • 何でも良いので、始点から終点までをつなぐパス P を1つ見つける
    • ただし、キャパシティがゼロ(= 全く流れない)のエッジは使わない
  • パス P に流すことができる最大まで流す
    • P を構成するエッジのうち、一番キャパシティが小さいところがボトルネック
  • 流したエッジはその分だけキャパシティが減る
  • 以上を、流せるパスが見つからなくなるまで繰り返す

処理の流れ

  1. フロー変数 \(f = 0\) とする
  2. 各エッジと逆向きに、キャパシティがゼロのエッジを張る
  3. グラフ上で、キャパシティがゼロでない(= まだ流す余地がある) エッジからなる始点〜終点のパス P を1つ見つける
    • パス P の各エッジのキャパシティのうち、最小のものを \(C_{\rm min}\) とする
    • 見つからなかったら処理終了
  4. パス P に対し、以下の処理を行う
    • パス P の各エッジのキャパシティを \(C_{\rm min}\) だけ減らす
    • パス P の各エッジの逆エッジのキャパシティを \(C_{\rm min}\) だけ増やす
    • \(f\) を \(C_{\rm min}\) だけ増やす
  5. 3に戻る

【NOTE】逆向きエッジの役割

重要な特性として、逆向きエッジのキャパシティ初期値はすべてゼロなので、

  • 最低一度は元のエッジにフローが流れないと、逆向きエッジには全くフローを流すことができない
  • 逆向きエッジを流れることができるフローは、元のエッジを流れるフロー以上にはできない

逆エッジにフローを流すとき、その逆エッジ、すなわち元のエッジのキャパシティが増える。
これは、元のエッジを通るフローを減らすことに等しい。
つまり、それ以前のパス探索で流すと決めたフローをキャンセルしている。

具体例

例題として、以下の有向グラフにおける S → T の最大フロー問題を考える(エッジ上の数値はキャパシティを表す)。

図1

キャパシティゼロの逆向きエッジを張る:

図2

図3

S → T のパスを1つ見つけ、流せるだけ流す(1回目):

図4

図5

S → T のパスを1つ見つけ、流せるだけ流す(2回目):

図6

図7

S → T のパスを1つ見つけ、流せるだけ流す(3回目):

図8

図9

これ以上流せるパスがない:

図10

結果、以下のように流すときに最大フロー6が実現できる(エッジ上の表記は 実際の流量/キャパシティ を表す)。

図11

【NOTE】

この手法で求まる流れ方はあくまで解の1つであり、同じ最大フローを満たす別の流れ方は存在し得る。