ネットワークフロー問題
ネットワークフロー問題（ネットワークフローもんだい、英: network flow problems）とは、組合せ最適化の（グラフの辺上に容量の値が課せられた）フローネットワークにおいて各頂点において入るフローと出るフローが同じ量でかつすべての辺において流れるフローがその辺の容量以下となるようなフローを求める問題である[1]。
ネットワークフロー問題における特筆すべき問題としては以下のものが挙げられる:
- 最大流問題：フローネットワークにおいて始点となる頂点から終点となる頂点へ向けてフローを流すとき、最大のフローとなるものを求める問題である[1]:166-206。
- 最小費用流問題：辺に単位当たりのフローを流すのにかかる費用が与えられたフローネットワークにおいて始点から終点へ向けて決められた量のフローを流すときに、最小の費用で流すものを求める問題である[1]:294-356。
- 多品種流問題：フローネットワークにおいてそれぞれ相異なる複数のフローを同時に流すときに最小の費用となるものを求める問題である[1]:649-694。
最大流最小カット定理では最大流問題における最大流の値がフローネットワークの頂点のに分割を考え、そらを結ぶ辺の重みの和が最小となる頂点分割を求める最小カット問題の重みの和の値と一致することが知られている。また、近似最大流最小カット定理は、最大流最小カット定理を多品種流問題に拡張した定理である。無向フローネットワークでのゴモリー・フー木は任意の二つの頂点における最小カットを得ることができる。
フローを構築的に求めるアルゴリズムとしては以下のものが知られている:
- ディニッツ法：最大流問題に対する強多項式時間アルゴリズム[1]:221-223
- エドモンズ・カープ法：効率よく最大流問題の最適解を求める強多項式時間アルゴリズム
- フォード・ファルカーソン法：最大流問題に対する解法で貪欲法の一種である。一般的な問題に対しては強多項式時間アルゴリズムではない。
- ネットワーク単体法：線形計画問題に対する解法の単体法をネットワークフロー問題に特化させたアルゴリズム[1]:402-460
- アウトオブキルタ法：最小費用流問題に対する解法[1]:326-331
- プリフロープッシュ法：最大流問題に対して最も効率よく解くことができる解法の一種。
これらに挙げられる問題以外を解く方法としては線形計画問題として定式化を与えることが多くの場合で可能であり、それにより線形計画問題を解く最適化ソルバにより解くことが可能である。