最大流・最小カット

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：最短経路問題（ダイクストラ・ベルマンフォード）・線形計画の双対性　|　関連：最小費用流・輸送問題

要点（BLUF）

最大流：始点 $s$ から終点 $t$ へ、各辺の容量を超えずに流せる最大の流量。
最小カット： $s$ と $t$ を切り離すのに必要な、除去する辺容量の最小合計。
最大流最小カット定理：両者の値は一致する。これは LP 双対（線形計画の双対性）の最も美しい実例。

概念 ── 流せる量と塞ぐ量

ネットワーク（パイプ網・通信網）で、始点 $s$ から終点 $t$ へどれだけ流せるか。各辺 $(u,v)$ には容量 $c(u,v)$ があり、流量 $f(u,v)$ はそれを超えられない。中間ノードでは流入＝流出（保存則）。最大流問題：

\max\ |f| \quad \text{s.t.}\quad 0 \le f(u,v) \le c(u,v),\quad \sum_{u} f(u,v) = \sum_{w} f(v,w)\ (v\ne s,t)

カットは、ノードを $s$ 側 $S$ と $t$ 側 $T$ に分ける分割。カットの容量は $S$ から $T$ へ渡る辺容量の合計。最小カット問題は、この合計を最小にする分割を探す。

最大流最小カット定理

定理：任意のネットワークで、 $s$ - $t$ 最大流の値＝ $s$ - $t$ 最小カットの容量。

graph LR
  S["s 始点"] -->|"16"| A["a"]
  S -->|"13"| B["b"]
  A -->|"12"| C["c"]
  B -->|"14"| D["d"]
  C -->|"20"| T["t 終点"]
  D -->|"4"| T

直観：流せる量は、どこかの「ボトルネック（最も細い断面）」で頭打ちになる。その最も細い断面が最小カット。流量の上限を決めているのは最小カットだから、両者が一致する。弱双対（線形計画の双対性）「任意の流量 ≤ 任意のカット容量」が常に成り立ち、強双対で等号に達する ── まさに LP 双対の幾何的実体。

増加路アルゴリズム（Ford–Fulkerson）

残余グラフを作る（各辺の残り容量＋逆向きの取り消し辺）。
残余グラフで $s$ から $t$ への 増加路（augmenting path） を探す。
その路の最小残余容量だけ流す。残余グラフを更新。
増加路が無くなったら終了 ── そのとき流量が最大、 $s$ から残余グラフで到達できるノード集合が最小カット $S$ 。

逆向きの取り消し辺が、過去の流しすぎを「修正」できる点が肝。経路探索を BFS にすると Edmonds–Karp（ $O(VE^2)$ ）。

Pythonで最大流＝最小カットを確認

CLRS の古典例（6ノード）で最大流を計算する。

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import maximum_flow

# 容量行列 (s=0, t=5)。0->1:16, 0->2:13, 1->3:12, 2->1:4, 2->4:14, 3->2:9, 4->3:7, 3->5:20, 4->5:4
cap = np.array([
    [0, 16, 13,  0,  0,  0],
    [0,  0, 10, 12,  0,  0],
    [0,  4,  0,  0, 14,  0],
    [0,  0,  9,  0,  0, 20],
    [0,  0,  0,  7,  0,  4],
    [0,  0,  0,  0,  0,  0],
])
res = maximum_flow(csr_matrix(cap), source=0, sink=5)
print(f"最大流の値 = {res.flow_value}")
print(f"(最大流最小カット定理より、最小カット容量も同じ値)")

実行結果：

最大流の値 = 23
(最大流最小カット定理より、最小カット容量も同じ値)

最大流は 23。最大流最小カット定理により、このネットワークを $s$ - $t$ で分断する最小カットの容量も ちょうど 23。たとえば $\{s,a,c\}$ と $\{b,d,t\}$ に切ると、渡る辺は $s\to b\,(13)$ と… というように、最も細い断面の合計が 23 になる。流量を頭打ちにするボトルネックが、そのまま最小カット。

数式の直観的意味

最大流問題は LP（線形計画の標準形と幾何）で、その双対がちょうど最小カット問題になる。弱双対「流量 ≤ カット容量」は「どんな流れも、それが必ず通る断面の容量を超えられない」という当たり前の不等式。強双対（線形計画の双対性）が「最大流＝最小カット」を保証する ── LP 双対が無条件にギャップ0なのと同じ理由（ネットワーク LP は全ユニモジュラ、ネットワーク最適化章目次）で、しかも容量が整数なら最大流も整数（整数流定理）。この定理は応用が極めて広い：二部マッチング（割当問題（ハンガリアン法））・画像分割・プロジェクト選択・スポーツ順位の可能性判定 ── 多くの組合せ問題が最大流／最小カットに帰着する。「流せる量」と「塞ぐコスト」が双対で結ばれているという事実が、これらを統一的に解く鍵になる。

⚠️ よくある誤解・落とし穴

逆向き（取り消し）辺を忘れない：残余グラフに逆辺が無いと、過去の流しすぎを修正できず最大流に届かない。
無理数容量だと Ford–Fulkerson が収束しないことがある：BFS で増加路を選ぶ Edmonds–Karp なら多項式時間保証。
最小カットは複数あり得る：最大流から復元される $S$ （残余で $s$ から到達可能な集合）は1つの最小カット。
容量が整数なら最大流も整数（整数流定理）。だがコスト最小化（最小費用流・輸送問題）は別問題。