最大フロー問題または最大流問題（）とは、単一の始点から単一の終点へのフローネットワークで最大となるフローを求める問題である。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題である最小費用流問題の特殊ケースと見ることもできる。最小カット問題（）とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から終点への最大フローは始点から終点への最小カットと等しい。これを最大フロー最小カット定理と呼ぶ。2部グラフの最大マッチング問題（）とは、2部グラフの最大マッチングを求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける。有向グラフ formula_1 において、各枝 formula_2 の容量を formula_3 としたとき、始点 formula_4 から終点 formula_5 への最大フロー formula_6 を求める。この問題の解法アルゴリズムは多数存在する。これら以外にも解法アルゴリズムは多数存在し、参考文献（特に Goldberg and Tarjan 1988）を参照されたい。

出典:wikipedia