きままにものづくり

日々の気付いたことなんかを書いてます。

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

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

目次

  • 関連
  • 証明

関連

証明

前提

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

カットとは

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

カットの容量とは

カットの容量とは、カットに接するある方向のエッジの容量の和である。2つの方向があるので、ふたつ存在する。
上の図を用いて説明する。
エッジに書かれてる数字は、そのエッジに流すことのできる最大値(容量)を示す。
集合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へ向かうエッジが存在することになる。これは、仮定と矛盾する。

フローfの式は、
 f = x(S,T) - x(T,S)
である。
この式に、x(T,S)=0x(S,T)=U(S,T)という条件を代入すると、
 f = U(S,T)
となる。

つまり、f = U(S,T)となるfまたはU(S,T)は存在する。
 f \leq U(S,T)より、 f = U(S,T)を満たすfは最大フロー、U(S,T)となるカットは最小カットである。

そしてf=U(S,T)より、最小カットの容量と最大フローは等しい。

広告を非表示にする