4-2 最大流最小切断定理

$S$ の各頂点について「流出－流入」を足します。$S$ 内部のarcは、一方の頂点で流出、他方で流入として現れ相殺します。$S$ から $T$ へのarcは流出として一度、$T$ から $S$ へのarcは流入として一度残ります。
$S$ 内で保存則が課されないのはsource $s$ だけで、sinkは $T$ にあります。従って頂点ごとの左辺の和はsourceの正味流出 $|f|$ であり、右辺が表示したcut横断flowです。□

前補題から
$$ |f| =\sum_{\delta^+(S)}f(a)-\sum_{\delta^-(S)}f(a) \le\sum_{\delta^+(S)}f(a) \le\sum_{\delta^+(S)}c(a) =c(S,T). $$
第二項は非負flowを引いており、forward arcでは容量制約を使いました。□

$S$ から $T$ へのoriginal arc $a:u\to v$ で $f(a)< c(a)$ なら、正容量のforward residual arc $a^+:u\to v$ があります。$u$ は到達可能なので $v$ も到達可能となり、$v\in T$ に反します。従って飽和しています。
$T$ から $S$ へのoriginal arc $a:v\to u$ で $f(a)>0$ なら、正容量のbackward residual arc $a^-:u\to v$ があります。$u\in S$ から $v$ へ到達でき、やはり矛盾です。従ってflowは0です。□

cut横断flowの式と前補題から
$$ |f| =\sum_{\delta^+(S)}f(a)-\sum_{\delta^-(S)}f(a) =\sum_{\delta^+(S)}c(a)-0 =c(S,T). $$
□

2なら、residual到達集合から作ったcutが停止時等号を満たすので3です。
3なら、任意のfeasible flow $g$ に弱双対性を使って
$$ |g|\le c(S,T)=|f| $$
となるため、$f$ はmaximumで1です。
1なら2を示します。augmenting pathがあればaugmentation lemmaにより値が真に大きいfeasible flowを作れ、maximum性に反します。従ってpathはありません。
少なくともzero flowはfeasibleです。Ford--Fulkersonが有限停止する整数・有理容量では上の構成が直接maximumとminimum cutを与えます。一般の実容量でも、feasible flow全体は有限次元の閉有界集合でflow値は連続なのでmaximumが存在し、1から2、2から3により同じ結論を得ます。従って最大値と最小値は一致します。□

停止条件はresidual $s$--$t$ pathがないことです。max-flow min-cut定理の同値条件によりflowはmaximumで、到達集合のcut容量はその値に等しいためminimumです。□

「ネットワーク流」で、整数容量に対するFord--Fulkersonは有限停止し、全反復でflowのintegralityを保つことを証明しました。停止flowは前系によりmaximumです。cut容量は整数容量の和なので整数です。□

更新前後の距離を $d,d'$ とします。$d'(v)< d(v)$ となる頂点があると仮定し、新しいresidual graphの最短path上で最初にこの不等式が起こる頂点を $v$、その直前を $u$ とします。従って
$$ d'(u)\ge d(u),\qquad d'(v)=d'(u)+1. $$
arc $u\to v$ が更新前にもresidualなら
$$ d(v)\le d(u)+1\le d'(u)+1=d'(v), $$
となり矛盾です。従って $u\to v$ は更新により新しく生じたbackward residual arcです。つまり更新に使った最短pathは逆向きarc $v\to u$ を含み、
$$ d(u)=d(v)+1 $$
です。
最初の不等式と合わせると
$$ d'(v)=d'(u)+1\ge d(u)+1=d(v)+2, $$
これは $d'(v)< d(v)$ に反します。従って距離は減少しません。□

各augmentationでbottleneck residual arcが少なくとも一本飽和し、residual graphから消えます。このarc $u\to v$ をその反復へchargeします。最短path上にあるので
$$ d(v)=d(u)+1. $$
同じlabel付きresidual arc $u\to v$ が後に再び現れて、再度飽和chargeされるには、その間に逆向き $v\to u$ を通るaugmentationが必要です。その時点の距離を $\widetilde d$ とすると
$$ \widetilde d(u)=\widetilde d(v)+1. $$
距離非減少性から $\widetilde d(v)\ge d(v)=d(u)+1$ なので
$$ \widetilde d(u)\ge d(u)+2. $$
従って同じ向きのarcが再chargeされるたび、そのtailの距離は少なくとも2増えます。有限距離は高々 $|V|-1$ なので、各向きは $O(|V|)$ 回しかchargeされません。
original arc一つはforward・backwardの二つのlabel付きresidual向きを生むため、charge総数、従ってaugmentation回数は $O(|V||A|)$ です。一回のBFSと更新は $O(|A|)$ 時間なので、全体は $O(|V||A|^2)$ です。
有限回でresidual pathがなくなり、max-flow min-cut定理により出力はmaximumです。□

各arc容量を1とするnetworkを作ります。integral flow theoremによりintegral maximum flowがあります。各arc flowは0または1で、flow decompositionからcycleを除けば、値 $k$ のflowは $k$ 本の $s$--$t$ pathへ分解されます。容量1なのでpathはarcを共有しません。逆に $k$ 本のarc-disjoint pathへ各1流せば値 $k$ のflowです。従ってmaximum flow値はarc-disjoint path最大数です。
任意の $s$--$t$ cut $\delta^+(S)$ を削除すれば、$S$ 内の $s$ から $T$ 内の $t$ へ進めないためarc separatorです。容量1なのでcut容量はarc数です。
逆にarc separator $F$ を削除したグラフで $s$ から到達可能な頂点集合を $S$ とします。$t$ は到達不能なので $(S,V\setminus S)$ はcutです。元のグラフで $S$ から外へ出るarcは全て $F$ に属さなければならず、
$$ |\delta^+(S)|\le|F|. $$
従ってminimum cut容量はminimum separator数と一致します。max-flow min-cut定理から三つの量が等しいです。□

任意の $s$--$t$ cut $(S,T)$ を考えます。中間arc $x\to y$ が一つでも $S$ から $T$ へ出れば、cut容量は少なくとも $M=|X|+1>|X|$ です。
そのような中間arcがない場合、$A=S\cap X$ の全近傍は $S\cap Y$ に含まれます。cut容量には、$s$ から $X\setminus A$ への $|X|-|A|$ 本と、$S\cap Y$ から $t$ への $|S\cap Y|$ 本が寄与します。従ってHall条件から
$$ c(S,T) =|X|-|A|+|S\cap Y| \ge |X|-|A|+|N(A)| \ge |X|. $$
一方、cut $S=\{s\}$ の容量は $|X|$ です。従ってminimum cut値は $|X|$、max-flow min-cut定理から値 $|X|$ のmaximum flowがあります。容量が整数なのでintegral flowを選べます。このflowでは $s\to x$ と $y\to t$ の容量が1であるため、各中間arc $x\to y$ のflowも実際には0または1です。positive-flowの中間arcを辺として選ぶと、一つの $x$ からも一つの $y$ からも高々一本しか選ばれません。したがって「ネットワーク流」と同じ対応により大きさ $|X|$ のmatching、すなわち $X$ を飽和するmatchingを得ます。□

$S$ から外へ出るarcは $s\to b$、$a\to b$、$a\to t$ で、容量は3,2,3です。従って
$$ c(S,T)=3+2+3=8. $$
弱双対性により任意のfeasible flowは値8以下です。$b\to a$ のような逆向きarcがあってもcut容量には入りません。□

cut横断式から
$$ c(S,T)-|f| =\sum_{\delta^+(S)}(c(a)-f(a)) +\sum_{\delta^-(S)}f(a). $$
右辺の各項は非負です。左辺が0なら全項が0でなければならず、forward cut arcでは $f(a)=c(a)$、backward cut arcでは $f(a)=0$ です。□

path $s\to a\to t$ と $s\to b\to t$ へ各1流せるので値2です。cut $S=\{s\}$ の容量は $c(s,a)+c(s,b)=2$ です。弱双対性から値は2を超えず、flowとcutが同値2なので双方最適です。□

flow decompositionにより、flowは $s$--$t$ path flowとcycle flowへ分かれます。cycle flowはflow値へ寄与しないため除いても値3のままです。容量1かつintegralなので各path係数は1で、係数和3から三本のpathがあります。同じarcを二pathが使えばそのarc flowが2になり容量1に反するため、pathはarc-disjointです。□

path $s\to a\to t$ と $s\to b\to t$ はarc-disjointなので少なくとも2本です。sourceから出るarcは $s\to a,s\to b$ の二本だけで、これらを削除すれば全pathが消えます。従ってseparatorは2本以下で、Mengerの定理または直接の上界から最大path数も2以下です。よって両者とも2です。□

$S=\{s,a,b,c,1,2\}$、$T=\{t\}$ とします。全中間arcは $S$ 内部にあり、cutを出るのは $1\to t,2\to t$ の二本だけです。従って容量は2です。
max-flow値は2以下であり、integral flowとmatchingの対応からmatching辺数も2以下です。$|X|=3$ なので全員を飽和できません。これはHall障害 $|N(X)|=2<3$ と同じcut証明です。□