最大フロー問題

最大フロー問題（さいだいフローもんだい、）または最大流問題とは、単一の始点から単一の終点へのフローネットワークで最大となるフローを求める問題である。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題である最小費用流問題の特殊ケースと見ることもできる。

最小カット問題（）とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から終点への最大フローは始点から終点への最小カットと等しい。これを最大フロー最小カット定理と呼ぶ。

2部グラフの最大マッチング問題（）とは、2部グラフの最大マッチングを求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける。

解法 
有向グラフ  において、各枝  の容量を  としたとき、始点  から終点  への最大フロー  を求める。この問題の解法アルゴリズムは多数存在する。

これら以外にも解法アルゴリズムは多数存在し、参考文献（特に Goldberg and Tarjan 1988）を参照されたい。

脚注・出典

参考文献 
 
 
 
 

グラフ理論
オペレーションズリサーチ
数学に関する記事