|
最大フロー問題または最大流問題()とは、単一の始点から単一の終点へのフローネットワークで最大となるフローを求める問題である。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題である循環流問題の特殊ケースと見ることもできる。 最小カット問題()とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から終点への最大フローは始点から終点への最小カットと等しい。これを最大フロー最小カット定理と呼ぶ。 2部グラフの最大マッチング問題()とは、2部グラフの最大マッチングを求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける〔。 == 解法 == 有向グラフ において、各枝 の容量を としたとき、始点 から終点 への最大フロー を求める。この問題の解法アルゴリズムは多数存在する。 これら以外にも解法アルゴリズムは多数存在し、参考文献(特に Goldberg and Tarjan 1988)を参照されたい。 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「最大フロー問題」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Maximum flow problem 」があります。 スポンサード リンク
|