最大フロー最小カット定理

最大フロー最小カット定理は、最大フロー問題に関する定理である。
この定理は、「最大フローと最小カットの容量は等しい」ということを示す。

証明

前提

最大フロー問題においては、始点(source)と終点(sink)以外のノードでは、流入量=流出量という条件を満たす。

カットとは

カットとは、ひとつのノードの集合(グラフ)を、ノードsを含む集合Sとノードtを含む集合Tに分割することである。
ここで、ノードsは始点、ノードtは終点を示す。
カットの組み合わせは、 $2^{|V|-2}$ となる。Vはノードの数を示す。
下の図が具体例である。
f:id:even_eko:20130808225401p:plain

カットの容量とは

カットの容量とは、カットに接するある方向のエッジの容量の和である。２つの方向があるので、ふたつ存在する。
上の図を用いて説明する。
エッジに書かれてる数字は、そのエッジに流すことのできる最大値(容量)を示す。
集合Sから集合Tへのエッジの容量の和を $U(S,T)$ とし、集合Tから集合Sへのエッジの容量の和を $U(T,S)$ とする。
SからTへ向かうエッジは2本あるので、それの和をとると、 $U(S,T)=10$ となる。
TからSへ向かうエッジは2本あるので、それの和をとると、 $U(T,S)=9$ となる。

カットの容量とフローの関係

フローは、ノードsからの流出量またはノードtへの流入量と等しい。
つまり、フローはノードsからノードtへの流量になる。
集合Sからの流出量または集合Tへの流入量を $x(T,S)$ 、集合Tからの流出量または集合Sへの流入量を $x(S,T)$ とする。
以下の図が具体例である。
f:id:even_eko:20130808225410p:plain
前提より、s,t以外のノードでは流入量=流出量という条件を満たすので、フロー $f$ は集合Sから集合Tへの流量に等しくなる。
$f = x(S,T) - x(T,S)$
フローは必ず正の整数になるので、
$x(S,T) \geq x(T,S)$
よって、
$f \leq x(S,T)$
エッジの容量を超えて、流すことはできないので
$f \leq x(S,T) \leq U(S,T)$

最小カットと最大フローの関係

最小カットとは、 $U(S,T)$ が最小となるカットのことである。
フローは、カットに依存しないので、どのカットにおいても $f \leq U(S,T)$ は成り立つ。
つまり、最小カット $U_m(S,T)$ においても、
$f \leq U_m(S,T)$
は成り立つ。
これは、フローにおいての上界を、カットにおいての下界を示す。
よって、 $f = U_m(S,T)$ が存在するなら、その $f$ は最大フローとなる。
また、 $U(S,T) = f$ となるカットは、最小カットであるといえる。

$f = U(S,T)$ の存在

ここで、フォード-ファルカーソンにより、求まる残余ネットワークに注目する。
このアルゴリズムにより、sからtへのパスが存在しない残余ネットワークが求まる。
f:id:even_eko:20130809083316p:plain
sから到達可能なノードの集合をSとし、それ以外を集合Tとする。
f:id:even_eko:20130809083327p:plain
残余ネットワークにおいてsからtへのパスが存在しないので、 $x(T,S) = 0$ かつ $x(S,T)=U(S,T)$ となる。

これについて、背理法を用いて証明する。
残余ネットワークにおける茶色のエッジは、ネットワークフローにおけるエッジの逆辺に等しい。
ここで、残余ネットワークにおいてsからtへのパスが存在しなくても、 $x(T,S) \neq 0$ を満たすと仮定する。 $x(T,S) \neq 0$ ということは、集合Tから集合Sへと流れるエッジが存在するということである。ネットワークフローにおけるエッジの逆辺は残余ネットワークにおける茶色のエッジ、つまり集合Sから集合Tへのエッジに等しい。フローは集合Sから集合Tへの流量に等しくなる。よって、sからtへのパスが存在することになる。これは、仮定と矛盾する。
同様に背理法を用いて、 $x(S,T)=U(S,T)$ も証明できる。 $x(S,T) < U(S,T)$ ならば、残余ネットワークにおいて集合Sから集合Tへ向かうエッジが存在することになる。これは、仮定と矛盾する。