最大フロー問題
ネットワークの各区間に、同時に流せる量（容量）の上限があるとき、出発点から到着点まで、全体で同時に最大どれだけ流せるかを求める問題。最大の流量は、ネットワークを出発側と到着側に分ける切り口のうち、容量の合計が最も小さいもの（最小カット）の値に等しい。
イマシルちゃんの解説
水道管のネットワークを思い浮かべてみて。
太い管も細い管もあって、それぞれ流せる水の量に限りがあるんだ。
スタートからゴールまで、いろんな道を同時に使って、全部でどれだけ水を流せるかな？
答えは、途中の「いちばん細いところ」で決まっちゃうんだ。
ただし、その「細いところ」は、1本の管じゃなくて、何本かの管をまとめて見て探すのがポイントなんだよ。
より深い解説
定義
各辺（区間）に容量が決められたネットワークで、出発点（ソース）から到着点（シンク）へ流す量を、次の条件を守りながら最大にする問題である。
- 各区間に流す量は、その区間の容量を超えない
- 途中の点では、入る量と出る量が等しい
通信では、地点の間の論理回線の多重度（同時に使える回線数）を容量とみなし、2地点の間で同時に使える回線の最大数を求めるのに使う。
最大フロー最小カット定理
ネットワークの点を、出発点を含む組と、到着点を含む組の2つに分けたとき、2つの組をまたぐ区間を切ると、流れは止まる。この切り口をカットといい、またぐ区間の容量の合計をカットの容量という。
最大の流量 ＝ すべてのカットのうち、容量が最小のもの（最小カット）の値どこで切っても、流れはそのカットの容量を超えられない。そして、最も細いカットまでは、必ず流すことができる。
例
| 区間 | 容量 |
|---|---|
| S−A | 3 |
| S−B | 2 |
| A−B | 1 |
| A−T | 2 |
| B−T | 3 |
| カット（S側の組） | またぐ区間 | 容量 |
|---|---|---|
| {S} | S−A、S−B | 3＋2＝5 |
| {S、A} | A−T、A−B、S−B | 2＋1＋2＝5 |
| {S、B} | S−A、A−B、B−T | 3＋1＋3＝7 |
| {S、A、B} | A−T、B−T | 2＋3＝5 |
最小カットは5なので、最大の流量は5である。実際に、S→A→T に2、S→A→B→T に1、S→B→T に2を流すと、合計5になる。
解き方のコツ
- 出発点の周り、到着点の周りの容量の合計は、まず確かめる上限になる
- ただし、途中に細いところがあれば、そこが答えになる。出発点の周りや到着点の周りの合計だけで答えを決めない
- 経路を1本ずつ選んで、残りの容量を減らしながら流していく方法（フォード・ファルカーソン法）でも求められる