最大流問題

最大流問題 †

このページは競技プログラミングに興味のある方向けに最大流問題を簡単に説明するページです

最大流問題 †

最大流問題は重み付グラフが与えられたとき、辺をパイプ(フローと言う)、重みをパイプに流せる水の最大量と考えた時に
開始ノード(ソースと言う)から終了ノード(シンクと言う)までに流すことが出来る水の最大量を求める問題である

貪欲法で解けるんじゃない？ †

貪欲法と言っても以下のような方法だと解けないです
1.とりあえずソースに隣接する各ノードに目いっぱい流す
2.ノードの持つフローの中で最大容量の大きいフローから順に目いっぱい流す
3.2を繰り返す

解けそう †

以下のような場合を考えましょう。ソースはAでシンクはFです

これを、上述の貪欲法で導くと以下のようになります
分数表現された数値の分母はそのフローの最大流量を、分子は現時点の流量を示しています

となり、この場合のシンクへの流量は11となります

次に、上述の貪欲法の条件2を「最大流量の小さなフローから順に目いっぱい流す」に変更してみましょう

となり、この場合のシンクへの流量は12となります

しかし、以下のような流し方をするとシンクへの流量を13へと増加させることが出来ます

これでシンクへの流量が13になり、これが最大流量になります
つまり、貪欲法ではうまくいかないことがわかります

じゃぁどうすればいいの？ †

残余ネットワークという概念を導入することでシンプルに説明できますが、残余ネットワークを用いた説明は後述するとして
とりあえずザックリと説明します

1.ソースからシンクへ至る経路のうち、水を流せる経路を一つ選ぶ。水を流せる経路が存在しない場合4へ進む
2.1で選んだ経路を構成するフローの中で「追加で流せる水量(これを残余容量と言います)」が最小の値を持つフローを見つける
　(水を流せる経路ということは残余容量が0より大きいということです)
3.2で見つけたフローに流せる水量を1で選んだ経路に流す
4.この時点での流し方が最大流量となる

この時、注意すべき点が2点あります
1.「逆流」が可能であるということです。有向グラフであったとしても、手順1で経路を探す際に水の流れる向きを気にしなくても構いません
　ただし、有向なフローと無向なフローでは流量の適切な範囲が異なるので注意する必要があります
　例えば隣接したノードA,Bをつなぐフローの容量が8であったとして
　有向なフローの場合、流量として適切な範囲はこの場合、0〜8です
　したがって、A→Bの方向の流量が3の場合、A→Bの方向への残余容量は5ですが、B→Aの方向への残余容量は3です
　無向なフローである場合、流量は-8〜8の範囲でとれますので、この場合はA→Bの方向への残余容量は5ですが、B→Aの方向への残余容量は13です
2.ある時点で水を流すことのできない経路であってもほかの経路に水を流す際に「逆流」が起こった場合、「水を流すことのできる経路」になる場合があります
　したがって、全経路を列挙して、順番にチェックするという手法は使えません。

ほんとにこれでうまくいくの？ †

実際にやってみましょう

まず、A→D→Fの経路を調べます。この経路でもっとも残余容量が小さいフローはA→Dの経路で6なので、水を6流します

A→B→D→Fの経路を調べます。同様にD→Fの残余容量が1で最小なので水を1流します

A→B→E→Fの経路を調べます。同様にB→Eの残余容量が4で最小なので水を4流します

A→B→C→E→Fの経路を調べます。同様にC→Eの残余容量が2で最小なので水を2流します

はい、先に挙げたとおりの流し方と一致しましたね。

残余ネットワークってなんですか？ †

残余ネットワークとはある2つのノード間においてどの方向へどれだけの水を流すことが出来るかということを有向な辺を用いて示したものになります
つまり、「各ノード間には(逆向きの)有向な辺が2つある」ということになりその向きは逆になっているということです
このようにすることで各種探索手法を用いて「水を流すことのできる経路」を比較的容易に探索することが出来ます

おまけ †

このページで説明した「最大流量問題」は「最小カット問題」と呼ばれる問題を解く際に応用できます
最小カット問題とは

重みつき連結グラフの辺を除去していくことを考える。この時、辺を除去するコストは各辺の重みに等しい。
ノードSとTについてSとTを結ぶパスが存在しなくなるように辺を除去するのに必要なコストの最小値を求めよ

という問題です。このとき、最小のコストはノードSをソース、ノードTをシンクとした時の最大流量に等しくなります(証明は割愛)