Rustコトハジメ

プログラミング言語Rustに関する情報をお届けします。

フォードファルカーソン法の復習

一回理解したと思ったんですが、もう一度読んだら全く理解不能だったため、蟻本に書いてあることを自分の言葉で書き直して復習します。

フォードファルカーソン法というのは、辺の容量が与えられたネットワークにおいてs-tの最大流を求めるアルゴリズムです。

方針としては、まずはアルゴリズムを偶然発見してから、最小カットが最大流であるという証明を後付けします。

「出来るだけがんばって流す」という貪欲法をしても最大流は得られないので、残余グラフというものを考えます。

残余グラフは、流量を減らす方向に巻き戻すことが出来る逆向きの辺(容量は正向きの流量)を付け加えたグラフです。このグラフにおいて流せなくなるまで貪欲に流し続けるというのがフォードファルカーソン法です。

この証明は、アルゴリズムの結果、残余グラフにおいてこれ以上流せなくなった時のフローがf'であるという事実を利用します。

sから流すことの出来る最大のノード集合をSとします。(sからtには流せないことがわかっているため、tはSに含まれないことがわかります。つまりグラフは必ず2分できます)この時、SとV\Sの境界を考えると、Sに対する仮定から、SからV\Sに向かう辺はマックスまで流しきってるとわかります。逆にV\Sの辺に少しでも流れているとすると、それを巻き戻す逆辺の容量が0以上となって、SからV\Sに流すことが出来てしまうため、Sの仮定に反します。従って0です。

ところで、任意のs-tカットについて、fの流量は(Sから出る辺の流量)-(Sに入る辺の流量)であることがわかります。Sに入る辺の流量は0以上なので、fの流量 <= カット容量が言えます。

話をさきほどのs-tカットに戻すと、f'の流量 = (Sから出る辺の流量)-0 = カット容量となっており、このs-tカットにおいて可能な最大の流量であることがわかります。もしこれ以上大きな流量を流そうとしても、少なくともこのs-tカットにはこれ以上は流せないため、これが求める最大流だとわかります。

また、もしこのカットより容量の小さいカットが存在する仮定すると、最大流はもっと小さくなってしまうため、これが最小カットであることもわかります。

従って最小カットが最大流であることが示されました。