フローネットワークの最小カットの容量を求めるアルゴリズム
アルゴリズム
\(|f^*|\) が最小カットの容量
最小カットの容量を求めるアルゴリズム:
フローネットワーク \(G=(V,E)\) の最大フロー \(f^*\) の値 \(|f^*|\) を求める\(|f^*|\) が最小カットの容量
...
Ford-Fullkerson法による最大フローの値を求めるアルゴリズム
アルゴリズム
ソース(入口) からシンク(出口)までの増加可能経路 \(p\) が残余ネットワーク \ ...
最大フローを求めるアルゴリズム(Ford-Fullkerson法):
フロー \(f\) を 0 としてはじめるソース(入口) からシンク(出口)までの増加可能経路 \(p\) が残余ネットワーク \ ...
フローネットワークの基礎と用語の定義
フローフローとフローネットワーク
関数 \(f : V×V \rightarrow \mathbb{R}\)で表現されるフローは、以下の特徴を持つ重み付き有向グラフ(フローネットワーク) \(G=(V,E)\) 上で定義されます。