最大流と最小カット

試験が残り一つなので適当に蟻本を読んでみることにした。

最大流
…グラフにおいてs(source)からt(sink)に水を流したときに最大どのくらい流せるか？

蟻本にのっていたように、最初にdfsでsからtまで限界まで水を流す。
その後、水を押し戻したりして最大になるように頑張る、というのが基本。

ちゃんとした言葉にすると、f(e)をフロー、c(e)をcapacityとすると、f(e) < c(e)である辺と、c(e) > 0である辺の逆辺を用いて(このようなグラフを残余グラフという)dfsをすれば良い。これだけである。(Ford-Fulkersonの定理)

また、これを証明するのに最小カットという概念を使う。
最小カット
…グラフにおいてsからtへ水が流せないように辺をカットするとき、カットしなければいけない辺
のcostの和の最小値。

任意のs-tカットにおいて、(S, V/S)を考えると、(fの流量) = (Sから出る流量)-(Sに入る流量)であるので、(fの流量) <= (カットの容量) となる。Ford-Fulkersonの定理で求めたフローの残余グラフでsから行くことができる頂点の集合vをvとすると、vからv/Sへは、f(e) = c(e)、v/Sからvへはc(e) = 0となっているので、(fの流量) = (カット)となる。ゆえに(最小カット) = (最大流)であることがわかる。