フローネットワーク

アルゴリズム

最小カットの容量を求めるアルゴリズム：

フローネットワーク \(G=(V,E)\) の最大フロー \(f^*\) の値 \(|f^*|\) を求める
\(|f^*|\) が最小カットの容量

...

アルゴリズム

最大フローを求めるアルゴリズム（Ford-Fullkerson法）：

フロー \(f\) を 0 としてはじめる
ソース(入口) からシンク(出口)までの増加可能経路 \(p\) が残余ネットワーク \ ...

フローフローとフローネットワーク

関数 \(f : V×V \rightarrow \mathbb{R}\)で表現されるフローは、以下の特徴を持つ重み付き有向グラフ（フローネットワーク） \(G=(V,E)\) 上で定義されます。