テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

フォードファルカーソン法のあとに最小カットが見つかる証明

蟻本の中級で説明されている最大流は, 多くのグラフ問題に応用出来るプロコン必須の概念である. 故に, 厳密でなくとも, 証明をして原理について理解を深めることに価値がある. 教科書やネット上に証明は転がっているが, ピンと来ないので, 私なりの言葉で書いておくことにした. 正しいかどうかは分からないが私的には納得した.

まず, 最大流=最小カットを超ざっくり説明すると, 「一番のボトルネックのところにマックス通すのが最大流になるに決まってんだろ」であるが, さすがにこれはざっくりすぎて何の価値もないので, もう少し丁寧に考える.

あるカットを考える. s側をS, t側をTとして, カット上のエッジについて, 容量の和U(from, to), 実際の流量x(from, to)を定義する. すると, 明らかにf = x(S, T) - x(T, S)である. さらに, x(T,S) > 0より, f <= x(S,T) <= U(S,T)が言える. 今, 仮に最小カットが見つかったとして, これをUmin(S,T)とする. この時, f = Umin(S,T)となるfがあるならば, このfを最大流fmaxとして不満ない.

フォードファルカーソンの結果, 最大流fmaxが求まったとする. この時の残余ネットについて, sから辿り着けるものと辿りつけないものに分離すると, そのカットにおいてfmax=U(S,T)が成立する. 仮にこれが最小カットでないとすると, さらに小さいカットがあるはずであるが, そうすると, フォードファルカーソンの結果求まったものがfmaxでないことになる. これは仮定に反するので, さきほどのU(S,T)は最小カットUmin(S,T)である.

以上より, フォードファルカーソンがfmaxを求めるならば, 残余ネットの境界は最小カットであることが証明された.