§E13.14Menger の定理

証明. 1 を示す。$G-E$は辺をもたないので、長さ$1$以上の道が存在しない。$s\ne t$であるから長さ$0$の道は$s$から$t$への道ではない。よって$G-E$に$s$-$t$道は存在せず、$E$は$s$-$t$辺切断である。

2 を示す。$T=V\setminus\{s,t\}$と置くと、$G-T$の頂点は$s$と$t$だけである。$s$と$t$は隣接しないので$G-T$は辺をもたず、1 と同じ理由で$s$-$t$道が存在しない。よって$T$は$s$-$t$頂点切断である。

3 を示す。$s$と$t$が隣接するとし、$T\subseteq V\setminus\{s,t\}$を任意にとる。辺$\{s,t\}$の両端点は$T$に属さないので、この辺は$G-T$の辺であり、$s,t$は$G-T$の$s$-$t$道である。よって$T$は$s$-$t$頂点切断ではない。▨

証明. 容量制約と整数性により、各弧で$f(a)\in\{0,1\}$であるから、$A_f$は$f$が値$1$をとる弧全体である。$k$についての数学的帰納法で示す。

$k=0$のときは、$0$本の道からなる空の族が主張を満たす。

$k\ge1$とし、値が$k-1$である場合について主張が成り立つと仮定する。

第一段:$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$である。したがって§E13.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$の弧だけを用い、どの二本も共通の弧をもたない。▨

証明.$S$を$s$-$t$カットとし、$E(S)$を、一方の端点が$S$に属し他方の端点が$V\setminus S$に属する$G$の辺の全体とする。辺$\{u,v\}\in E(S)$で$u\in S$、$v\notin S$であるものは、二つの弧$(u,v)$と$(v,u)$を与えるが、このうち始点が$S$に属し終点が$S$に属さないのは$(u,v)$だけである。逆に$\delta^{+}(S)$の各弧はこのようにして$E(S)$のちょうど一つの辺から生じる。すべての容量が$1$であるから$c(S)=\lvert\delta^{+}(S)\rvert=\lvert E(S)\rvert$である。

$E(S)$が$s$-$t$辺切断であることを示す。$G-E(S)$に$s$-$t$道$s=w_0,w_1,\dots,w_r=t$が存在すると仮定する。$w_0=s\in S$かつ$w_r=t\notin S$であるから、$w_{i-1}\in S$かつ$w_i\notin S$を満たす添字$i$が存在する。すると辺$\{w_{i-1},w_i\}$は$E(S)$に属し、$G-E(S)$の辺ではないので矛盾する。よって$E(S)$は$s$-$t$辺切断である。

逆に$F$を$s$-$t$辺切断とする。$G-F$において$s$から到達可能な頂点全体を$S_F$と置く。$s\in S_F$であり、$G-F$に$s$-$t$道が存在しないので$t\notin S_F$である。よって$S_F$は$s$-$t$カットである。一方の端点$u$が$S_F$に属し他方の端点$v$が$S_F$に属さない辺$\{u,v\}$をとると、この辺が$F$に属さないならば$G-F$において$v$が$s$から到達可能となり$v\notin S_F$に反する。したがってそのような辺はすべて$F$に属し、$c(S_F)=\lvert E(S_F)\rvert\le\lvert F\rvert$である。

以上より、$s$-$t$カットの容量の最小値と$s$-$t$辺切断の濃度の最小値は互いに他以下であり、等しい。▨

証明. 辺版のネットワーク$D_G$を考える。辺素な$s$-$t$道は互いに辺を共有せず各々が少なくとも一本の辺を用いるので、その本数は$\lvert E\rvert$以下である。また命題 1.3 (1)により$s$-$t$辺切断は少なくとも一つ存在する。よって$\kappa$と$\lambda$はいずれも定まる。

第一段:$\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$以上である。§E13.12 定理 5.1により最大フローの値は最小カットの容量に等しく、補題 3.1によりそれは$\lambda$に等しい。よって$\kappa\le\lambda$である。

第二段: 逆平行な対の除去。容量はすべて$1$であるから§E13.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$となり、第二段の仮定に反する。よって$P_1,\dots,P_\lambda$は辺素であり、$\kappa\ge\lambda$である。

第一段と第三段より$\kappa=\lambda$である。▨

証明.(1)を示す。$D'_G$の弧の形から、$s$を始点とする弧は$(s,v^{-})$（$v\in W$、$\{s,v\}\in E$）だけであり、$v^{-}$を始点とする弧は$(v^{-},v^{+})$だけであり、$v^{+}$を始点とする弧は$(v^{+},u^{-})$（$\{v,u\}\in E$、$u\in W$）または$(v^{+},t)$（$\{v,t\}\in E$）だけである。$t$を始点とする弧は無い。よって$s$から$t$への有向道は、$s$から$v_1^{-}$へ移り、以後$v_i^{-}$から$v_i^{+}$へ、$v_i^{+}$から$v_{i+1}^{-}$へ移ることを繰り返し、最後に$v_r^{+}$から$t$へ至る形をとる。有向道の頂点は相異なるから$v_1,\dots,v_r$は相異なり、構成から$\{s,v_1\}$、$\{v_i,v_{i+1}\}$、$\{v_r,t\}$はいずれも$E$に属する。よって$s,v_1,\dots,v_r,t$は$G$の$s$-$t$道である。逆に$G$の$s$-$t$道$s,v_1,\dots,v_r,t$をとると、$s$と$t$が隣接しないので$r\ge1$であり、上の形の頂点の列が$D'_G$の有向道を与える。頂点弧についての主張は構成から明らかである。

(2)を示す。まず、$s$-$t$頂点切断$T$が与えられたとする。頂点弧$(v^{-},v^{+})$（$v\in T$）をすべて取り除いた有向グラフにおいて$s$から到達可能な$D'_G$の頂点全体を$S$と置く。$s\in S$である。$t\in S$であると仮定すると、取り除いた弧を用いない$s$から$t$への有向道が存在し、(1)によりそれは$G$の$s$-$t$道$s,v_1,\dots,v_r,t$に対応し、頂点弧$(v_i^{-},v_i^{+})$をすべて用いる。取り除いた弧を用いないことから$v_i\notin T$（$1\le i\le r$）であり、この道は$G-T$の$s$-$t$道である。これは$T$が$s$-$t$頂点切断であることに反する。よって$t\notin S$であり、$S$は$s$-$t$カットである。$\delta^{+}(S)$の弧$a$をとると、$a$が取り除いた弧でないならば$a$の終点は$s$から到達可能となり$S$に属するので、$a\in\delta^{+}(S)$に反する。よって$\delta^{+}(S)$は取り除いた弧の集合に含まれ、容量がすべて$1$であるから$c(S)\le\lvert T\rvert$である。

逆に、$s$-$t$カット$S$が与えられたとする。$\delta^{+}(S)$の各弧$a$に対し、$W$の頂点$\psi(a)$を次のように定める。$a=(v^{-},v^{+})$のとき$\psi(a)=v$、$a=(s,v^{-})$のとき$\psi(a)=v$、$a=(u^{+},v^{-})$のとき$\psi(a)=v$、$a=(v^{+},t)$のとき$\psi(a)=v$とする。$T=\{\psi(a):\ a\in\delta^{+}(S)\}$と置くと$T\subseteq W$であり、$\lvert T\rvert\le\lvert\delta^{+}(S)\rvert=c(S)$である。$T$が$s$-$t$頂点切断であることを示す。$G$の$s$-$t$道$s,v_1,\dots,v_r,t$をとり、(1)が与える$D'_G$の有向道を考える。この有向道は$s\in S$から出発し$t\notin S$で終わるので、始点が$S$に属し終点が$S$に属さない弧$a$を少なくとも一つ含む。$a\in\delta^{+}(S)$であり、四つの場合のいずれにおいても$\psi(a)$は$v_1,\dots,v_r$のいずれかである。よってこの道は$T$の頂点を通り、$G-T$の道ではない。$G$の任意の$s$-$t$道についてこれが成り立つので、$G-T$に$s$-$t$道は存在せず、$T$は$s$-$t$頂点切断である。

以上より、$s$-$t$カットの容量の最小値と$s$-$t$頂点切断の濃度の最小値は互いに他以下であり、等しい。▨

証明. 頂点版のネットワーク$D'_G$を考える。命題 1.3 (2)により$s$-$t$頂点切断は少なくとも一つ存在するので$\lambda_V$は定まる。内点素な$s$-$t$道は互いに内点を共有せず、$s$と$t$が隣接しないので各々が少なくとも一つの内点をもつから、その本数は$\lvert V\rvert$以下であり$\kappa_V$も定まる。

第一段:$\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$以上であり、§E13.12 定理 5.1と補題 4.2 (2)により、最大フローの値は$\lambda_V$に等しい。ゆえに$\kappa_V\le\lambda_V$である。

第二段:$\kappa_V\ge\lambda_V$。容量がすべて$1$であるから§E13.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$である。

第一段と第二段より$\kappa_V=\lambda_V$である。▨