定理
相異なる始点 $s$ と終点 $t$ を持つ有限有向ネットワーク $G=(V,E)$ を考える。各有向辺 $e$ には有限かつ非負の容量 $c_e$ が与えられている。実行可能なフローとは、各辺に値 $f_e$ を割り当て、
\[0\leq f_e\leq c_e\]| を満たし、$s,t$ 以外のすべての頂点で流入量と流出量が等しくなるものである。フローの値 $ | f | $ は $s$ から出る正味のフローであり、これは $t$ に入る正味のフローに等しい。 |
$s$–$t$ カットとは、$V=S\mathbin{\dot\cup}T$、$s\in S$、$t\in T$ を満たす頂点集合の分割である。カット容量は、元の有向辺のうち始点が $S$ に属し終点が $T$ に属する辺の容量の総和として定義する。
\[c(S,T)=\sum_{e=(u,v)\in E:\ u\in S,\ v\in T} c_e.\]最大フロー最小カット定理は、実行可能なフローの最大値が、すべての $s$–$t$ カット容量の最小値に等しいと述べる。
証明
まず、任意の実行可能なフロー $f$ と任意の $s$–$t$ カット $(S,T)$ を取る。$S$ の頂点についてフロー保存則を合計すると、両端が $S$ にある辺のフローは相殺され、
\[|f|=\sum_{e=(u,v):\,u\in S,v\in T}f_e-\sum_{e=(u,v):\,u\in T,v\in S}f_e\]| を得る。第2の和の各項は非負であり、第1の和では各辺のフローは容量以下なので、$ | f | \leq c(S,T)$ である。これはすべての実行可能なフローとすべてのカットについて成り立つ。 |
ネットワークは有限で容量もすべて有限であるため、実行可能なフローの集合は有限次元空間における空でないコンパクト集合であり、最大フロー $f$ が存在する。その残余グラフを作る。元の各辺 $u\to v$ に対して、順方向の残余辺の容量は $c_e-f_e$、逆方向の残余辺 $v\to u$ の容量は $f_e$ である。残余辺はそれぞれ対応する元の辺と区別して扱う。正の容量を持つ残余辺をたどって $s$ から到達できる頂点の集合を $S$、$T=V\setminus S$ とする。$f$ は最大フローなので、$t$ は到達可能ではない。もし到達可能なら、残余グラフに $s$ から $t$ への道があり、その道に沿って正の量だけフローを増やし、フロー値をさらに大きくできるからである。
$S$ から $T$ へ向かう正容量の残余辺は存在しない。したがって、$S$ から $T$ へ向かう元の辺はすべて飽和しており、$f_e=c_e$ である。また、$T$ から $S$ へ向かう元の辺については、それぞれの逆向き残余辺が $S$ から $T$ へ向かうため、その残余容量は0でなければならず、従って $f_e=0$ である。これらを先ほどのカットの式に代入すると、
\[|f|=\sum_{e=(u,v):\,u\in S,v\in T}c_e=c(S,T)\]を得る。したがって、この最大フローの値はこのカットの容量に等しい。すべてのフローはすべてのカット容量以下なので、このフローは最大であり、このカットは最小である。両者の値は等しく、定理が示された。∎