最大フロー問題と最小カット問題とFord-Fulkersonのアルゴリズム
algorithm最大フロー問題
最大フロー問題は容量を持つパスで構成されるネットワークでのソースからシンクまでのフローを最大化する問題。 各パスを流れるフローがその容量を超えず各ノードに入る量と出る量が乖離しないようにソースからシンクまで全量を送る必要がある。
最小カット問題
ソースとシンクを分断するカットの容量の最小値を求める問題。ノードの部分集合S⊆Vから出ていくパスの集合を カット (S,V\S) 、その容量の和をカットの容量という。
Ford-Fulkersonのアルゴリズム
ソースからシンクまでのパスがあれば送れるだけ送り、送った分の容量を持つ逆向きのパスを追加するというのをパスがなくなるまで繰り返して最大フローを求める。 この際、容量が残っているパスのみからなるグラフを剰余ネットワークという。
最大フローを F とすると計算量は O(F|E|) となるが、実際は1ずつしか最大フローを更新できないケースはまずないのでそれほど遅くない時間で実行できる。
証明
ソースから到達できるノードの部分集合をSとすると、上記のアルゴリズムを終えた状態の剰余ネットワークVにおいて(S,V\S)はソースとシンクを分断するカットとなる。VにソースからシンクへのパスがないということはSからV\Sへのパスの容量は全て使われていてV\SからSへのパスは何も流れていないということになるので、その場合のフローはカットの容量と一致する。フローがカットの容量を上回ることはないのでこれより大きくすることはできない。
また、最大フローと最小カットが一致することも導かれる。これを 最大フロー最小カット定理 といい、最小カット部分がボトルネックになっている。
