§E16.14Menger の定理

$A_f$の弧だけで$s$から$t$へ至る有向道が存在すること。$V$を頂点集合とし$A_f$を弧集合とする有向グラフにおいて、$s$から到達可能な頂点全体を$S$と置く。$t\notin S$であると仮定する。このとき$S$は$s$-$t$カットである。$a\in\delta^{+}(S)$をとると、$a$の始点は$S$に属し終点は$S$に属さないので$a\notin A_f$であり、$f(a)=0$である。したがって§E16.12 命題 2.2の等式により

となり、$k\ge1$に反する。よって$t\in S$であり、$A_f$の弧だけを用いる$s$から$t$への有向道$P$が存在する。

値を一つ減らすこと。$P$に現れる弧の集合を$A(P)$と書き、

と定める。$A(P)\subseteq A_f$であるから、$a\in A(P)$では$f'(a)=0$であり、容量制約$0\le f'(a)\le1$はすべての弧で成り立つ。保存則を確かめる。$P$の頂点はすべて相異なるので、$s$と$t$以外の各頂点$v$について、$v$が$P$に現れるならば$v$を終点とする$P$の弧と$v$を始点とする$P$の弧がちょうど一本ずつあり、$v$へ入る流量と$v$から出る流量がともに$1$ずつ減る。$v$が$P$に現れないならば$v$に接する弧の流量は変わらない。よって$f'$は保存則を満たし、フローである。値については、$P$は$s$を始点とする弧をちょうど一本含み、$s$を終点とする弧を含まないので

である。また$f'$は各弧で整数値をとり、$A_{f'}=A_f\setminus A(P)$である。

帰納法の適用。帰納法の仮定を$f'$へ適用すると、$A_{f'}$の弧だけを用い、どの二本も共通の弧をもたない$s$から$t$への有向道が$k-1$本存在する。$A_{f'}$は$A(P)$と交わらないので、これらの道はいずれも$P$と共通の弧をもたない。したがってこれらに$P$を加えた$k$本の道は、$A_f$の弧だけを用い、どの二本も共通の弧をもたない。

$\kappa\le\lambda$。辺素な$s$-$t$道$P_1,\dots,P_k$をとる。各$P_i$を$s$から$t$へたどり、通る辺$\{u,v\}$を進む向きに合わせて弧$(u,v)$へ読み替える。こうして得られる弧の全体で値$1$、他の弧で値$0$をとる写像を$f$とする。$P_i$の頂点はすべて相異なるので、一つの道が同じ辺を二度通ることはなく、相異なる道は辺素であるから共通の辺をもたない。したがって、どの弧も高々一本の道から値$1$を与えられ、$f$は矛盾なく定まり容量制約$0\le f\le1$を満たす。

保存則を確かめる。頂点$v\in V\setminus\{s,t\}$をとる。$v$が$P_i$の内点であるならば、$P_i$から生じる弧のうち$v$を終点とするものと$v$を始点とするものがちょうど一本ずつある。$v$が$P_i$の端点になることは$v\ne s,t$より無く、$v$が$P_i$に現れないならば$P_i$は$v$に接する弧を与えない。各道の寄与を足し合わせると、$v$へ入る流量と$v$から出る流量は等しい。よって$f$はフローである。値については、各$P_i$が$s$を始点とする弧をちょうど一本与え、$s$を終点とする弧を与えないので$\operatorname{val}(f)=k$である。

したがって最大フローの値は$\kappa$以上である。§E16.12 定理 5.1により最大フローの値は最小カットの容量に等しく、補題 3.1によりそれは$\lambda$に等しい。よって$\kappa\le\lambda$である。

逆平行な対の除去。容量はすべて$1$であるから§E16.12 系 6.3により、各弧で整数値をとる最大フローが存在する。その一つを$f$とし、$\operatorname{val}(f)=\lambda$である。辺$\{u,v\}$が生む二つの弧について$f(u,v)=f(v,u)=1$が成り立つとき、この二つの弧の値をともに$0$に置き換える。得られる写像$g$もフローである。実際、$g$は二つの弧$(u,v)$と$(v,u)$で値$0$をとり、他の弧では$f$と同じ値をとる。$f$は各弧で整数値をとり容量制約を満たすので、すべての弧で$f$の値は$0$または$1$であり、したがって$g$の値も各弧で$0$または$1$である。容量はすべて$1$であるから$g$は容量制約を満たす。保存則については、頂点$u$を始点とする弧$(u,v)$の流量と$u$を終点とする弧$(v,u)$の流量がともに$1$ずつ減るので、$u$へ入る流量と$u$から出る流量の差は変わらず、頂点$v$についても同様に差は変わらない。$u$と$v$のいずれかが$s$である場合も、$s$から出る流量と$s$へ入る流量がともに$1$ずつ減るので$\operatorname{val}(g)=\operatorname{val}(f)$である。この置き換えは値$1$をとる弧の本数を$2$減らすので、有限回で終わる。以下、$f$は最大フローであって、どの辺についても、その辺が生む二つの弧が同時に値$1$をとることは無いとしてよい。

$\kappa\ge\lambda$。$f$は各弧で整数値をとる値$\lambda$のフローであるから、補題 2.2により、値$1$をとる弧だけを用い、どの二本も共通の弧をもたない$s$から$t$への有向道$Q_1,\dots,Q_\lambda$が存在する。各$Q_i$の弧を、それを生んだ$G$の辺へ読み替えると、頂点の列としては$Q_i$と同じ$s$-$t$道$P_i$が得られる。

$P_1,\dots,P_\lambda$が辺素であることを示す。相異なる$i,j$について$P_i$と$P_j$が辺$\{u,v\}$を共有すると仮定する。$Q_i$と$Q_j$は共通の弧をもたないので、一方が$(u,v)$を、他方が$(v,u)$を用いる。すると$f(u,v)=f(v,u)=1$となり、(2)の仮定に反する。よって$P_1,\dots,P_\lambda$は辺素であり、$\kappa\ge\lambda$である。

$\kappa_V\le\lambda_V$。内点素な$s$-$t$道$P_1,\dots,P_k$をとる。各$P_i$に補題 4.2 (1)の対応を適用して$D'_G$の有向道$Q_i$を得る。$Q_i$の弧の全体で値$1$、他の弧で値$0$をとる写像を$f$とする。

相異なる$i,j$について$Q_i$と$Q_j$が共通の弧をもたないことを示す。共通の弧を$a$とすると、$a$の四つの形のいずれにおいても、$a$の端点に現れる添字の頂点、すなわち$a=(v^{-},v^{+})$、$a=(s,v^{-})$、$a=(u^{+},v^{-})$、$a=(v^{+},t)$のそれぞれについての$v$は、$P_i$の内点であり$P_j$の内点でもある。これは$P_i$と$P_j$が内点素であることに反する。よってどの弧も高々一本の$Q_i$に現れ、$f$は矛盾なく定まって容量制約を満たす。

保存則を確かめる。$D'_G$の頂点のうち$s$と$t$以外のものは$v^{-}$または$v^{+}$（$v\in W$）である。$Q_i$が$v^{-}$を通るならば、$Q_i$は$v^{-}$を終点とする弧と$v^{-}$を始点とする弧をちょうど一本ずつ含む。$v^{+}$についても同様である。$Q_i$が通らない頂点には$Q_i$からの寄与が無い。各$Q_i$の寄与を足し合わせると保存則を得る。値については、各$Q_i$が$s$を始点とする弧をちょうど一本与え、$D'_G$には$s$を終点とする弧が無いので$\operatorname{val}(f)=k$である。

よって最大フローの値は$\kappa_V$以上であり、§E16.12 定理 5.1と補題 4.2 (2)により、最大フローの値は$\lambda_V$に等しい。ゆえに$\kappa_V\le\lambda_V$である。

$\kappa_V\ge\lambda_V$。容量がすべて$1$であるから§E16.12 系 6.3により、各弧で整数値をとる最大フロー$f$が存在し、$\operatorname{val}(f)=\lambda_V$である。補題 2.2により、値$1$をとる弧だけを用い、どの二本も共通の弧をもたない$s$から$t$への有向道$Q_1,\dots,Q_{\lambda_V}$が存在する。補題 4.2 (1)により、各$Q_i$は$G$の$s$-$t$道$P_i$に対応する。

$P_1,\dots,P_{\lambda_V}$が内点素であることを示す。相異なる$i,j$について$P_i$と$P_j$が共通の内点$v$をもつと仮定する。補題 4.2 (1)により、$Q_i$と$Q_j$はいずれも頂点弧$(v^{-},v^{+})$を用いる。これは$Q_i$と$Q_j$が共通の弧をもたないことに反する。よって$P_1,\dots,P_{\lambda_V}$は内点素であり、$\kappa_V\ge\lambda_V$である。