maximum-flow-problem.md

layout	entry
changelog	summary authors reviewers date 記事作成 kimiyuki 2021-04-01 00:00:00 +0900
algorithm	input output time_complexity space_complexity aliases level 最大流問題 maximum flow problem blue
description	最大フロー問題とは、与えられたネットワークのフローであって流量が最大のものを求めるという問題。 最大フロー最小カット定理によって最大フロー問題の解の流量は最小カット問題の解の容量に等しい。

最大フロー問題

概要

最大フロー問題とは、与えられたネットワークのフローであって流量が最大のものを求めるという問題である。 最大フロー最小カット定理によって最大フロー問題の解の流量は最小カット問題の解の容量に等しい。

詳細

(省略)

その他

• フローの定義では「始点から終点へと向かうフローと無関係な位置に閉路状のフローがないこと」は要求されていない。最大フローを求めるアルゴリズムはこのような閉路状のフローを含む出力をすることがあるので、出力されたフローの構成を利用する際には注意が必要である。なお、最大フロー問題の解から流量を変えずにこのような閉路状のフローを取り除くことは常に可能である。

関連項目

• 最小カット問題
  • 最大フロー最小カット定理によって最大フロー問題の解の流量は最小カット問題の解の容量に等しい。
• Dinic 法
  • Dinic 法は最大フロー問題を解くアルゴリズムである。最悪計算量は $O(\lvert V \rvert^2 \cdot \lvert E \rvert)$ だが実用的にはかなり速い。
• Ford-Fulkerson 法
  • Ford-Fulkerson 法は最大フロー問題を $O(F \cdot \lvert E \rvert)$ で解く代表的なアルゴリズムである。