§E16.12最大フロー最小カット定理

証明. 各頂点$v\in V$に対し

と置く。保存則により$v\in V\setminus\{s,t\}$では$b(v)=0$であり、値の定義により$b(s)=\operatorname{val}(f)$である。$S$は$s$を含み$t$を含まないので、$S$の要素は$s$か、または保存則の成り立つ頂点である。したがって

が成り立つ。

左辺を弧ごとに数え直す。自己ループが無いので、弧$a=(u,v)$の始点と終点は相異なる。$a$が$\sum_{v\in S}b(v)$へ寄与する仕方は次の四通りである。$u\in S$かつ$v\in S$のとき、$b(u)$に$+f(a)$、$b(v)$に$-f(a)$として現れて相殺する。$u\in S$かつ$v\notin S$のとき、すなわち$a\in\delta^{+}(S)$のとき、$b(u)$に$+f(a)$としてだけ現れる。$u\notin S$かつ$v\in S$のとき、すなわち$a\in\delta^{-}(S)$のとき、$b(v)$に$-f(a)$としてだけ現れる。$u\notin S$かつ$v\notin S$のとき、寄与は無い。したがって

となり、主張の等式を得る。

不等式を示す。容量制約により$f(a)\ge0$であるから、右辺の第二の和は非負であり、これを落とすと上からの評価になる。さらに各$a\in\delta^{+}(S)$で$f(a)\le c(a)$であるから

が成り立つ。▨

証明.$K=1+\sum_{a\in A}\lvert\alpha(a)\rvert$と置く。$K\ge1>0$である。$x,y\in\R^{A}$に対し、各$a\in A$について

が成り立つ。三角不等式により

を得る。$\varepsilon>0$に対して$\delta=\varepsilon/K>0$と置けば、$\rho_2(x,y)<\delta$のとき$\lvert L(x)-L(y)\rvert<\varepsilon$が成り立つ。したがって$L$は各点で連続である。▨

証明.$A=\emptyset$のときは$\R^{A}$が一点集合であり、$F$はその一点からなり、$\operatorname{val}$は$0$という値だけをとるので主張は成り立つ。以下$A\ne\emptyset$とし、$n=\lvert A\rvert\ge1$と置く。

空でないこと。各弧で値$0$をとる写像はフローであるから$F\ne\emptyset$である。

有界であること。$C=\max_{a\in A}c(a)$と置く。$f\in F$ならば各$a$で$0\le f(a)\le C$であるから

が成り立つ。したがって$F$は原点を中心とする半径$\sqrt n\,C+1$の開球に含まれ、有界である。

閉であること。各$a\in A$について$\Phi_a(x)=x(a)$と置き、各$v\in V\setminus\{s,t\}$について

と置く。自己ループが無いので$\delta^{-}(v)$と$\delta^{+}(v)$は交わらず、$K_v$は係数が$1$、$-1$または$0$である線形汎関数である。$\Phi_a$も線形汎関数であるから、補題 3.1によりこれらはすべて連続である。

$F$の補集合が開であることを示す。$g\in\R^{A}\setminus F$とすると、次の三つの場合のいずれかが起こる。

• ある$a_0\in A$について$\Phi_{a_0}(g)<0$である。$\varepsilon=-\Phi_{a_0}(g)>0$に対する$\Phi_{a_0}$の連続性の$\delta>0$をとると、$\rho_2(x,g)<\delta$を満たす$x$は$\Phi_{a_0}(x)<\Phi_{a_0}(g)+\varepsilon=0$を満たすので、$x\notin F$である。
• ある$a_0\in A$について$\Phi_{a_0}(g)>c(a_0)$である。$\varepsilon=\Phi_{a_0}(g)-c(a_0)>0$に対する$\delta>0$をとると、$\rho_2(x,g)<\delta$を満たす$x$は$\Phi_{a_0}(x)>\Phi_{a_0}(g)-\varepsilon=c(a_0)$を満たすので、$x\notin F$である。
• ある$v_0\in V\setminus\{s,t\}$について$K_{v_0}(g)\ne0$である。$\varepsilon=\lvert K_{v_0}(g)\rvert>0$に対する$\delta>0$をとると、$\rho_2(x,g)<\delta$を満たす$x$は$\lvert K_{v_0}(x)-K_{v_0}(g)\rvert<\varepsilon$を満たすので$K_{v_0}(x)\ne0$であり、$x\notin F$である。

いずれの場合も$g$の周りの開球が$F$と交わらない。したがって$F$の補集合は開であり、$F$は閉である。

値の連続性。$\alpha(a)=1$（$a\in\delta^{+}(s)$のとき）、$\alpha(a)=-1$（$a\in\delta^{-}(s)$のとき）、$\alpha(a)=0$（それ以外のとき）と定めると、自己ループが無いので$\delta^{+}(s)$と$\delta^{-}(s)$は交わらず、$\alpha$は矛盾なく定まる。このとき$\operatorname{val}(x)=\sum_{a}\alpha(a)x(a)$であるから、補題 3.1により$\operatorname{val}$は$\R^{A}$上で連続である。連続性は$\varepsilon$と$\delta$による条件であるから、定義域を部分集合$F$へ制限したものも、$F$に$\R^{A}$の距離を入れた部分空間の上で連続である。

結論。$A$の要素に$1$から$n$まで番号を付けると、$\R^{A}$は Euclid 距離を保ったまま$\R^{n}$と同一視される。従属選択公理のもとで§E2.9 定理 4.3を$\R^{n}$の有界閉集合$F$へ適用すると、$F$はコンパクトである。ここで用いるコンパクト性も、次に用いる連続性も、距離から定まる位相についてのものである。実際、§E2.4 定義 1.1の意味での連続性は、§E2.4 定理 2.1により、開集合の逆像が開集合であることと同値であり、これが位相空間の写像としての連続性である。$F\ne\emptyset$であり$\operatorname{val}:F\to\R$は距離から定まる位相について連続であるから、§E2.19 定理 4.4により$\operatorname{val}$は$F$の上で最大値をとる。最大値を与える$f\in F$が最大フローである。▨

証明. $f'$が矛盾なく定まること。増加道$P$の頂点はすべて相異なる。弧$a=(u,v)$について$a^{+}$と$a^{-}$がともに$P$に現れたとすると、$P$は$u$から$v$への移動と$v$から$u$への移動をともに含むので、$u$と$v$がそれぞれ二度現れることになり、頂点が相異なることに反する。また、同じ残余弧が$P$に二度現れることも、頂点が相異なることに反する。したがって上の場合分けは重複せず、$f'$は矛盾なく定まる。

容量制約。$P$に現れない弧では$f'=f$であるから制約は保たれる。$a^{+}$が$P$に現れるときは$\Delta\le c_f(a^{+})=c(a)-f(a)$であるから

が成り立つ。$a^{-}$が$P$に現れるときは$\Delta\le c_f(a^{-})=f(a)$であるから

が成り立つ。

保存則と値。各頂点$w$について$b(w)=\sum_{a\in\delta^{+}(w)}f(a)-\sum_{a\in\delta^{-}(w)}f(a)$と置き、$f'$について同様に定めたものを$b'(w)$と書く。$P$に現れる残余弧$r$の始点を$x$、終点を$y$とすると、$r$による流量の変更が$b$に与える差は次のとおりである。$r=a^{+}$かつ$a=(x,y)$のときは$f(a)$が$\Delta$だけ増え、$a\in\delta^{+}(x)$かつ$a\in\delta^{-}(y)$であるから、$b(x)$は$\Delta$だけ増え$b(y)$は$\Delta$だけ減る。$r=a^{-}$かつ$a=(y,x)$のときは$f(a)$が$\Delta$だけ減り、$a\in\delta^{+}(y)$かつ$a\in\delta^{-}(x)$であるから、やはり$b(x)$は$\Delta$だけ増え$b(y)$は$\Delta$だけ減る。いずれの場合も、残余弧の始点で$+\Delta$、終点で$-\Delta$の差が生じる。

増加道を$s=w_0,\,r_1,\,w_1,\,\dots,\,r_k,\,w_k=t$と書く。各$r_i$は$w_{i-1}$を始点、$w_i$を終点とする。頂点$w_i$（$0<i<k$）は$r_i$の終点かつ$r_{i+1}$の始点であるから、差の総和は$-\Delta+\Delta=0$であり$b'(w_i)=b(w_i)=0$となる。$P$に現れない頂点では流量が変わらないので$b'=b$である。よって$f'$は保存則を満たし、フローである。$s=w_0$は$r_1$の始点であって、どの$r_i$の終点でもないから$b'(s)=b(s)+\Delta$であり、$\operatorname{val}(f')=\operatorname{val}(f)+\Delta$を得る。▨

証明. (1)$\Rightarrow$(2). 対偶を示す。$D_f$に増加道$P$が存在すると仮定する。補題 4.2により、$\operatorname{val}(f')=\operatorname{val}(f)+\Delta(P)$を満たすフロー$f'$が存在する。$\Delta(P)>0$であるから$\operatorname{val}(f')>\operatorname{val}(f)$となり、$f$は最大フローではない。

(2)$\Rightarrow$(3).$D_f$において$s$から到達可能な頂点全体を$S$と置く。長さ$0$の有向道により$s\in S$である。仮定により$s$から$t$への有向道は存在しないので$t\notin S$である。したがって$S$は$s$-$t$カットである。

$a=(u,v)\in\delta^{+}(S)$をとる。$u\in S$かつ$v\notin S$である。もし$f(a)<c(a)$であるとすると、順方向残余弧$a^{+}$が$D_f$に存在し、$u$から$v$へ移ることができるので$v\in S$となって矛盾する。よって$f(a)=c(a)$である。

$a=(v,u)\in\delta^{-}(S)$をとる。$u\in S$かつ$v\notin S$である。もし$f(a)>0$であるとすると、逆方向残余弧$a^{-}$が$u$を始点とし$v$を終点として$D_f$に存在するので$v\in S$となって矛盾する。よって$f(a)=0$である。

これらを命題 2.2の等式へ代入すると

を得る。

(3)$\Rightarrow$(1).$\operatorname{val}(f)=c(S)$を満たす$s$-$t$カット$S$をとる。任意のフロー$f'$について命題 2.2により$\operatorname{val}(f')\le c(S)=\operatorname{val}(f)$が成り立つので、$f$は最大フローである。

最大フローと最小カットの一致。命題 3.2により最大フロー$f^{*}$が存在する。(1)$\Rightarrow$(2)と(2)$\Rightarrow$(3)により$\operatorname{val}(f^{*})=c(S^{*})$を満たす$s$-$t$カット$S^{*}$が存在する。任意の$s$-$t$カット$S'$について命題 2.2により$c(S')\ge\operatorname{val}(f^{*})=c(S^{*})$であるから、$S^{*}$は最小カットであり、最大フローの値と最小カットの容量はともに$\operatorname{val}(f^{*})$に等しい。▨

証明. 不変条件。ループ不変条件（§D2.8 定義 1.1）として「現在の$f$はフローであり、各弧で整数値をとる」をとる。初期化では、各弧で値$0$をとる写像がフローであり整数値をとるので成り立つ。維持を示す。$f$が整数値をとるフローであるとき、各弧$a$で$c(a)-f(a)$と$f(a)$はともに整数であるから、残余容量はすべて正の整数であり、選んだ増加道$P$のボトルネック$\Delta(P)$は正の整数である。補題 4.2により増加操作の結果$f'$はフローであり、各弧で$f'(a)$は$f(a)$に整数を加えるか引くかしたものであるから整数値をとる。よって不変条件は保たれる。

停止性。$S_0=\{s\}$と置くと、$s\ne t$であるから$S_0$は$s$-$t$カットである。容量が整数であるから$c(S_0)$は非負整数である。ループの状態に対して

と定める。ここで$\Phi$は変量を表す記号であり、頂点集合$V$とは無関係である。不変条件により$\operatorname{val}(f)$は整数であり、命題 2.2により$\operatorname{val}(f)\le c(S_0)$であるから、$\Phi$は非負整数である。本体を一度実行すると、上に述べたとおり$\Delta(P)$は正の整数であるから$\operatorname{val}(f)$は$1$以上増え、$\Phi$は狭義に減少する。したがって§D2.8 命題 1.4により手続きは有限回の反復で停止する。

終了。停止時にはループの継続条件が偽であり、残余ネットワークに増加道が存在しない。不変条件により停止時の$f$はフローであって各弧で整数値をとるから、定理 5.1 (2)$\Rightarrow$(1)により$f$は整数値をとる最大フローである。以上の三段は§D2.8 定理 1.2の形の議論であり、手続きは停止して最大フローを返す。▨

証明.命題 6.1により、Ford–Fulkerson 法は有限回で停止し、停止時のフローは各弧で整数値をとる最大フローである。これが求める最大フローである。▨