10.1. Menger の定理

本章では最初に Menger の定理 (Menger's theorems) と呼ばれる一連の結果を見ていく。この定理は Karl Menger にちなんで名付けられており、彼は 1927 年に曲線のトポロジーに関する研究の補助的な結果として Menger の定理の一つを発見した (この定理の歴史については [Schrij03, § 9.6e] を参照してほしい)。

フィラデルフィアからニューヨークに車で移動するルートが \(4\) つあるとしよう。それぞれのルートは異なる道路を使う (\(2\) つ以上のルートに利用される道路は存在しない) と仮定する。このとき、どんな \(3\) つの道路が封鎖されたとしても、フィラデルフィアからニューヨークに行くルートは少なくとも一つ必ず残る。

これは明らかである (実際、封鎖される道路はそれぞれが \(4\) つのルートの最大でも一つを利用不可能にするので、\(3\) つの道路が封鎖された場合でも少なくとも \(1\) つのルートは利用可能なままとなる)。この逆はより興味深い問題になる: フィラデルフィアとニューヨークの間にある道路が十分に複雑で、任意の \(3\) つの道路を封鎖してもフィラデルフィアからニューヨークまで移動できるとする。このとき、フィラデルフィアからニューヨークへの同じ道路を使わない \(4\) つのルートが必ず存在すると言えるだろうか？

Menger の定理を使うと、この問題 (および設定を少し変えた様々な問題) の答えが「存在する」だと分かる。大まかに言って、Menger の定理に含まれる命題はどれも「ある場所から別の場所へ向かう路からなる任意の二要素が独立した集合の最大要素数は、出発地点と到着地点を分離するボトルネックからなる集合の最小要素数に等しい」ことを主張する。ここで「場所」は頂点または頂点の集合を意味し、「独立した」は「共通の弧を持たない」または「共通の内部頂点を持たない」または「共通の頂点を一切持たない」を意味し、「ボトルネック」は「取り除くと出発地点と終着地点が切り離される弧の集合または頂点の集合」を意味する。本書で証明する Menger の定理を次の表にまとめる¹:

• 有向グラフに関する命題:

  \[ \def\arraystretch{1.33} \begin{array}{|c|c|c|c|}\hline \text{定理} & \text{「場所」} & \text{「独立」} & \text{「ボトルネック」} \\\hline\hline \href{/graph/more-about-path/mengers-theorem/#thm.menger.da1}{\text{定理 10.1.6}} & \text{頂点} & \text{弧素} & \text{弧} \\\hline \href{/graph/more-about-path/mengers-theorem/#thm.menger.da2}{\text{定理 10.1.10}} & \text{頂点} & \text{弧素} & \text{カットの弧}\\\hline \href{/graph/more-about-path/mengers-theorem/#thm.menger.dam}{\text{定理 10.1.18}} & \text{頂点の集合} & \text{弧素} & \text{カットの弧} \\\hline \href{/graph/more-about-path/mengers-theorem/#thm.menger.dv2}{\text{定理 10.1.32}} & \text{頂点} & \text{内部頂点素} & \text{頂点} \in V\setminus\left\{ s,t\right\} \\\hline \href{/graph/more-about-path/mengers-theorem/#thm.menger.dvm}{\text{定理 10.1.36}} & \text{頂点の集合} & \text{内部頂点素} & \text{頂点} \in V\setminus\left( X\cup Y\right) \\\hline \href{/graph/more-about-path/mengers-theorem/#thm.menger.dvm-vd}{\text{定理 10.1.39}} & \text{頂点の集合} & \text{頂点素} & \text{頂点} \in V\\\hline \end{array} \]

• 無向グラフに関する命題:

  \[ \def\arraystretch{1.33} \begin{array}{|c|c|c|c|}\hline \text{定理} & \text{「場所」} & \text{「独立」} & \text{「ボトルネック」}\\\hline\hline \href{/graph/more-about-path/mengers-theorem/#thm.menger.ue1}{\text{定理 10.1.22}} & \text{頂点} & \text{辺素} & \text{辺}\\\hline \href{/graph/more-about-path/mengers-theorem/#thm.menger.ue2}{\text{定理 10.1.25}} & \text{頂点} & \text{辺素} & \text{カットの辺}\\\hline \href{/graph/more-about-path/mengers-theorem/#thm.menger.uv2}{\text{定理 10.1.42}} & \text{頂点} & \text{内部頂点素} & \text{頂点} \in V\setminus\left\{ s,t\right\} \\\hline \href{/graph/more-about-path/mengers-theorem/#thm.menger.uvm}{\text{定理 10.1.44}} & \text{頂点の集合} & \text{内部頂点素} & \text{頂点} \in V\setminus\left( X\cup Y\right) \\\hline \href{/graph/more-about-path/mengers-theorem/#thm.menger.uvm-vd}{\text{定理 10.1.45}} & \text{頂点の集合} & \text{頂点素} & \text{頂点} \in V\\\hline \end{array} \]

[他にも命題は作れるものの、紙面は限られている。]

10.1.1有向グラフの弧に関する Menger の定理

最も自然な設定を最初に考える: 道路網は有向グラフで、道路は (一方向にだけ通行できる) 弧だとする。まず、定理の主張を短く表現するのに役立つ概念をいくつか定義する:

例 10.1.2

弧素な二つの路 \(\mathbf{p}\) と \(\mathbf{q}\) の例を次に示す。\(\mathbf{p}\) のラベルは \(\mathbf{p}\) に含まれる弧を表し、\(\mathbf{q}\) のラベルは \(\mathbf{q}\) に含まれる弧を表す:

弧素でない二つの路 \(\mathbf{r}\) と \(\mathbf{s}\) の例を次に示す。「\(\mathbf{r},\mathbf{s}\)」のラベルは \(\mathbf{r}\) と \(\mathbf{s}\) に共通する弧を表す:

例 10.1.4

\(D=\left( V,A,\psi\right) \) を次の多重有向グラフとする:

このとき、集合 \(\left\{ \alpha,\gamma\right\} \) は \(s\)-\(t\)-弧切断でない (青く示した \(s\) から \(t\) への路が存在するため)。これに対して、集合 \(\left\{ \beta,\gamma\right\} \) と \(\left\{ \delta,\varepsilon\right\} \) はどちらも \(s\)-\(t\)-弧切断である。当然、\(\left\{ \beta,\gamma\right\} \) または \(\left\{ \delta,\varepsilon\right\} \) を部分集合として含む任意の \(V\) の部分集合も \(s\)-\(t\)-弧切断となる。

以上の定義を使えば、最初の Menger の定理を表明できる:

例 10.1.7

\(D\) を例 10.1.4 の多重有向グラフとする。このとき、\(s\)-\(t\)-弧切断の最小要素数は \(2\) である (実際、\(\left\{ \beta,\gamma\right\} \) が \(s\)-\(t\)-弧切断であり、要素数が \(1\) の \(s\)-\(t\)-弧切断が存在しないことは容易に分かる)。よって定理 10.1.6 より、\(s\) から \(t\) への路からなる任意の二要素が弧素な集合の最大要素数も \(2\) だと分かる。実際、\(s\) から \(t\) への弧素な二つの路は容易に見つけられる。具体的には次の図で青と赤で示された路である:

定理 10.1.6 を証明する前に、この定理の別バージョンを一つ表明する。こちらの方が証明される命題に近い。その別バージョンを表明するには、次の定義が必要になる:

\(s\)-\(t\)-カットがこの名前で呼ばれるのは、\(s\)-\(t\)-カットに含まれる弧を除去すると \(s\) と \(t\) が切り離されるためである。正確に言えば、次の命題が成り立つ:

[証明] \(B\) を任意の \(s\)-\(t\)-カットとする。\(B\) が \(s\)-\(t\)-弧切断だと示せばよい。言い換えれば、\(s\) から \(t\) への任意の路が \(B\) に属する弧を少なくとも一つ含むと証明する必要がある。

\(B\) が \(s\)-\(t\)-カットだから、\(B=\left[ S,\overline {S}\right] \) と \(s\in S\) と \(t\notin S\) を満たす \(V\) の部分集合 \(S\) が存在する。この \(S\) に注目する。

\(s\) から \(t\) への任意の路を \(\mathbf{p}\) とする。\(s \in S\) より \(\mathbf{p}\) は \(S\) に属する頂点から始まり、\(s \notin S\) より \(\mathbf{p}\) は \(S\) に属さない頂点で終わる。よって、\(\mathbf{p}\) はどこかで \(S\) から脱出する ── つまり、\(S\) に属する始点と \(S\) に属さない終点を持つ弧を含む。ここから \(\mathbf{p}\) は \(\left[ S,\overline{S}\right] \) に属する辺を含むと分かる。\(B=\left[ S,\overline{S}\right] \) だから、\(s\) から \(t\) への任意の路 \(\mathbf{p}\) は \(B\) に属する辺を含む。言い換えれば、\(B\) は \(s\)-\(t\)-弧切断である (弧切断の定義より)。以上で Remark 10.1.9 は証明された。□

例 10.1.11

\(D\) を次の多重有向グラフとする:

このとき、\(s\) から \(t\) への路からなる任意の二要素が弧素な集合の最大要素数は \(3\) である。実際、次の図に赤、青、茶で示した \(3\) つの路は任意の二つが弧素である:

要素数が \(3\) より大きい \(s\) から \(t\) への路の集合は、弧素でない二つの路を必ず含む。なぜなら (例えば) \(s\) が外向き弧を \(3\) つしか持たないからである。

定理 10.1.10 によれば、\(D\) の \(s\)-\(t\)-カットの最小要素数も \(3\) に等しい。要素数 \(3\) の \(s\)-\(t\)-カットはいくつか存在する。例えば「明らかな」カット \(\left[ \left\{ s\right\},\, \overline{\left\{ s\right\} }\right] \) は要素数 \(3\) の \(s\)-\(t\)-カットであり、\(\left[ \left\{ s,a,f\right\},\, \overline{\left\{ s,a,f\right\} }\right] \) も要素数 \(3\) の \(s\)-\(t\)-カットである。

\(D\) の \(c\) から \(e\) への弧の向きを反転させたグラフを考える (このとき茶色の路が無効になる)。このグラフ \(D^{\prime}\) を示す:

この有向グラフ \(D^{\prime}\) では、\(s\) から \(t\) への路からなる任意の二要素が弧素な集合の最大要素数は \(2\) である。実際、\(s\)-\(t\)-カット \(\left[ \left\{ s,c\right\},\, \overline{\left\{ s,c\right\} }\right] \) (\(s\) から \(t\) への弧と \(s\) から \(b\) への弧からなる) の要素数が \(2\) なので、\(s\)-\(t\)-カットの最小要素数は \(2\) 以下であり、定理 10.1.10 より \(s\) から \(t\) への路からなる任意の二要素が弧素な集合の最大要素数も \(2\) 以下と分かる。後者の値がちょうど \(2\) であることは容易に分かる (赤色の路と青色の路は \(D^{\prime}\) にも存在する)。

これまでに表明した二つの Menger の定理を証明するには、ネットワークに関する補題を一つ証明する必要がある。第 9.1 節の定義と定義 9.4.1 を思い出した上で、さらに記法を定義する:

これらの記法は自然に期待される性質を持つ: 例えば \(A\) から \(\mathbb{N}\) への写像の点ごとの和は結合性を持つ。つまり、写像としての等式 \(\left( f+g\right) +h=f+\left( g+h\right) \) が成り立つので、両者を \(f + g + h\) と書ける。また、不等式を通常通りに変形することもできる。例えば \(f-g\leq h\) が成り立つのは \(f \leq g + h\) が成り立つとき、かつそのときに限る。これらの命題はどれも簡単に確かめられる。

次の定義は Remark 9.1.8 で考えたフローを形式的に成文化したものである:

例 10.1.14

次のネットワークを考える:

全ての弧の容量は \(1\) とする。このとき、路 \(\mathbf{p}=\left( s,2,6,t\right) \) からは次の路フロー \(f_{\mathbf{p}}\) が得られる:

図を簡潔するにするため、弧のラベルには「of \(1\)」を書いていない。そのため弧に付いているラベル「\(1\)」は「\(1\) of \(1\)」と、「\(0\)」は「\(0\) of \(1\)」と解釈するべきである。

つまりネットワークにおける \(s\) から \(t\) への路に含まれる全ての弧が十分な容量を持っていれば、その路は路フローというフローに変換できる。もし \(s\) から \(t\) への \(m\) 個の路 \(\mathbf{p}_{1}\), \(\mathbf{p}_{2}\), ..., \(\mathbf{p}_{m}\) が存在して対応する弧が十分な容量を持っていれば、値 \(m\) のフロー \(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots+f_{\mathbf{p}_{m}}\) が得られる (一般に、後者のフローから \(\mathbf{p}_{1}\), \(\mathbf{p}_{2}\), ..., \(\mathbf{p}_{m}\) を一意に復元することはできない: フローが「混じり合って」識別不可能になる可能性がある)。

この観察の (ほぼ) 逆を示すのが次の補題である: 値が \(m\) の任意のフロー \(f\) は、\(m\) 個の (必ずしも相異なるとは限らない) \(s\) から \(t\) への路 \(\mathbf{p}_{1}\), \(\mathbf{p}_{2}\), ..., \(\mathbf{p}_{m}\) に対応する \(m\) 個の路フロー \(f_{\mathbf{p}_{1}}\), \(f_{\mathbf{p}_{2}}\), ..., \(f_{\mathbf{p}_{m}}\) の和 \(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots+f_{\mathbf{p}_{m}}\) を含む。ここで「含む」とは \(f\) が \(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots +f_{\mathbf{p}_{m}}\) に等しいことではなく、不等式 \(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots+f_{\mathbf{p}_{m}}\leq f\) が成り立つことを意味する。この補題は次の通りである:

[証明] \(m\) に関する数学的帰納法で示す。

ベースケース: \(m = 0\) のとき主張は明らかである (和 \(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots+f_{\mathbf{p}_{m}}\) は零フローなので、容量制約から従う)。

再帰ステップ: \(m\) を正整数とする。\(m=m-1\) の場合に補題が成り立つと (帰納法の仮定として) 仮定する。これから \(m=m\) の場合に補題が成り立つことを証明する。

値 \(m\) を持つ \(N\) 上のフロー \(f\) を考える。\(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots+f_{\mathbf{p}_{m}}\leq f\) を満たす \(s\) から \(t\) への \(m\) 個の路 \(\mathbf{p}_{1}\), \(\mathbf{p}_{2}\), ..., \(\mathbf{p}_{m}\) が \(D\) に存在すると示せばよい。

最初に \(f_{\mathbf{p}}\leq f\) を満たす \(s\) から \(t\) への路 \(\mathbf{p}\) が \(D\) に存在することを示す。

\(A^{\prime}\colonequals \left\{ a\in A\mid f\left( a\right) >0\right\} \) と定め、\(D\) の全域部分有向グラフ \(D^{\prime}\colonequals \left( V,A^{\prime},\psi|_{A^{\prime}}\right) \) を考える。\(D^{\prime}\) に \(s\) から \(v\) への路が存在するような頂点 \(v \in V\) 全体の集合を \(S\) とする。このとき \(s \in S\) である (自明な路 \(\left( s\right) \) は \(D^{\prime}\) における \(s\) から \(s\) への路であるため)。

これから任意の弧 \(b\in\left[ S,\overline{S}\right] \) が \(f\left( b\right) =0\) を満たすことを示す。

[証明: 背理法で示す。ある弧 \(b\in\left[ S,\overline{S}\right] \) が \(f\left( b\right) \neq0\) を満たすと仮定する。この \(b\) に注目する。\(f\) はフローだから、フローの容量制約と \(f\left( b\right) \neq0\) より \(f\left( b\right) >0\) を得る。よって \(A^{\prime}\) の定義から \(b \in A^{\prime}\) を得る。ここから \(D^{\prime}\) の定義より \(b\) は \(D^{\prime}\) の弧だと分かる。

\(u\) を弧 \(b\) の始点、\(v\) を弧 \(b\) の終点とする。\(b\in\left[ S,\overline{S}\right] \) より \(u\in S\) と \(v \in \overline{S}\) が分かる。\(u \in S\) より、有向グラフ \(D^{\prime}\) には \(s\) から \(u\) への路 \(\mathbf{p}\) が存在する。この \(\mathbf{p}\) に注目する。路 \(\mathbf{p}\) の末尾に弧 \(b\) と頂点 \(v\) を付け足すと、\(D^{\prime}\) における \(s\) から \(v\) への歩道が得られる (\(b\) は \(D^{\prime}\) の弧であり、始点 \(u\) と終点 \(v\) を持つため)。よって有向グラフ \(D^{\prime}\) は \(s\) から \(v\) への歩道を持ち、命題 4.5.8 より \(s\) から \(v\) への路も持つ。よって \(S\) の定義より \(v \in S\) が言える。しかしこれは \(v\in\overline{S}=V\setminus S\) と矛盾する。この矛盾から仮定が偽だと分かる。これで示したい命題は証明された。]

任意の弧 \(b\in\left[ S,\overline{S}\right] \) が \(f\left( b\right) =0\) を満たすと分かった。つまり \(f\left( S,\overline{S}\right) =0\) が成り立つ (定義 9.1.5 (d) で定めた記法を使っている)。一方 \(s \in S\) だから、もし \(t \notin S\) なら 命題 9.3.2 (b) より次の等式が成り立つ:

しかし、これは \(\left\vert f\right\vert =m>0\) と矛盾する。つまり \(t \in S\) である。\(S\) の定義を使って言い換えれば、\(D^{\prime}\) には \(s\) から \(t\) への路 \(\mathbf{p}\) が存在する。この路 \(\mathbf{p}\) は \(D\) の路でもあり、\(f_{\mathbf{p}}\leq f\) を満たす²。よって \(f-f_{\mathbf{p}}\) は \(A\) から \(\mathbb{N}\) への写像である。さらに \(f-f_{\mathbf{p}}\) もフローであり³、その値は \(\left\vert f-f_{\mathbf{p}}\right\vert =m-1\) を満たす⁴。よって帰納法の仮定より、\(s\) から \(t\) への \(m-1\) 個の路 \(\mathbf{p}_{1}\), \(\mathbf{p}_{2}\), ..., \(\mathbf{p}_{m-1}\) であって \(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots+f_{\mathbf{p}_{m-1}}\leq f-f_{\mathbf{p}}\) を満たすものが \(D\) に存在する。\(\mathbf{p}_{m}\colonequals \mathbf{p}\) と定めれば \(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots+f_{\mathbf{p}_{m-1}}\leq f-f_{\mathbf{p}}=f-f_{\mathbf{p}_{m}}\) であり、ここから \(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots+f_{\mathbf{p}_{m}}\leq f\) を得る。

\(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots+f_{\mathbf{p}_{m}}\leq f\) を満たす \(s\) から \(t\) への \(m\) 個の路 \(\mathbf{p}_{1}\), \(\mathbf{p}_{2}\), ..., \(\mathbf{p}_{m}\) が \(D\) に存在すると分かったので、帰納ステップは完了した。以上で補題 10.1.15 は証明された。□

[定理 10.1.10 の証明] \(D\) の全ての弧に容量 \(1\) を割り当てることで、入口 \(s\) と出口 \(t\) を持つネットワーク \(N\) を構成する。明らかに、このネットワーク \(N\) のカットは \(D\) の \(s\)-\(t\)-カットに等しい。さらに、全ての弧の容量が \(1\) なので、\(N\) のカット \(\left[ S,\overline{S}\right] \) の容量 \(c\left( S,\overline{S}\right) \) は \(\left[ S,\overline{S}\right] \) の要素数に等しい。

最大フロー最小カット定理 (定理 9.4.3) によれば、フローの値の最大値はカットの容量の最小値に等しい。よって前段落の議論より、\(N\) 上のフローの値の最大値は \(D\) の \(s\)-\(t\)-カットの最小要素数に等しい。後は、\(s\) から \(t\) への路からなる任意の二要素が弧素な集合の最大要素数がフローの値の最大値だと示せばよい。しかし、ここまでに示してきた命題を使えばこの証明は難しくない:

• 値が \(m\) のフロー \(f\) からは、どの二つも弧素な \(s\) から \(t\) への \(m\) 個の路が得られる (補題 10.1.15 より \(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots+f_{\mathbf{p}_{m}}\leq f\) を満たす \(s\) から \(t\) への \(m\) 個の路 \(\mathbf{p}_{1}\), \(\mathbf{p}_{2}\), ..., \(\mathbf{p}_{m}\) の存在が分かる。この不等式より、これらの \(m\) 個の路の任意の二つは弧素だと分かる⁵)。よって次の不等式を得る:

  \[ \begin{aligned} & \left(s \text{ から } t \text{ への路からなる任意の二要素が弧素な集合の最大要素数}\right) \\ & \quad \geq\left( \text{フローの値の最大値}\right) \end{aligned} \]

• 逆に、もし \(s\) から \(t\) への \(m\) 個の路 \(\mathbf{p}_{1}\), \(\mathbf{p}_{2}\), ..., \(\mathbf{p}_{m}\) の任意の二要素が弧素なら、値が \(m\) のフローを構築できる (具体的には \(f_{\mathbf{p}_{1}}+f_{\mathbf{p}_{2}}+\cdots+f_{\mathbf{p}_{m}}\) がそのようなフローである⁶)。よって次の不等式を得る:

  \[ \begin{aligned} & \left( \text{フローの値の最大値}\right) \\ & \quad \geq\left( s \text{ から } t \text{ への路からなる任意の二要素が弧素な集合の最大要素数} \right) \end{aligned} \]

二つの不等式から次の等式を得る:

以上で定理 10.1.10 は証明された。□

ネットワークとフローを使わない定理 10.1.10 の証明も知られている。[Schrij17, Corollary 4.1b] などを参照してほしい。

[定理 10.1.6 の証明] \(s\) から \(t\) への路からなる任意の二要素が弧素な集合の最大要素数を \(x\)、\(s\)-\(t\)-カットの最小要素数を \(n_{c}\)、\(s\)-\(t\)-弧切断の最小要素数を \(n_{s}\) とする⁷。

定理 10.1.10 より \(x = n_{c}\) を得る。ここでの目標は \(x=n_{s}\) の証明である。

Remark 10.1.9 より、任意の \(s\)-\(t\)-カットは \(s\)-\(t\)-弧切断である。よって \(n_{s}\leq n_{c}\) が分かる。また、\(x\leq n_{s}\) は鳩の巣原理から容易に分かる⁸。二つの不等式と \(x = n_{c}\) より \(x = n_{s}\) を得る。以上で定理 10.1.6 は証明された。□

弧に関する Menger の定理は頂点の集合の組に関する命題に拡張できる:

例 10.1.19

有向グラフ \(D=\left( V,A,\psi\right) \) と共通要素を持たない \(V\) の部分集合 \(X\), \(Y\) の例を次に示す:

この有向グラフ \(D\) において、\(X\) から \(Y\) への路からなる任意の二要素が弧素な集合の最大要素数は \(2\) である。\(D\) が持つ弧素な二つの路を次の図に (赤と青で) 示す:

定理 10.1.18 は \(X\)-\(Y\)-カットの最小要素数も \(2\) だと主張する。実際、要素数が \(2\) の \(X\)-\(Y\)-カットは存在する:

[定理 10.1.18 の証明] 与えられた多重有向グラフ \(D=\left( V,A,\psi\right) \) を次の手順で改変し、新しい多重有向グラフ \(D^{\prime}=\left( V^{\prime },A^{\prime},\psi^{\prime}\right) \) を定義する:

• \(X\) に属する全ての頂点を一つの (新しい) 頂点 \(s\) に置き換え、\(Y\) に属する全ての頂点を一つの (新しい) 頂点 \(t\) に置き換える。形式的に表現すれば、\(V^{\prime} \colonequals \left( V\setminus\left( X\cup Y\right) \right) \cup\left\{ s,t\right\} \) と定める。ここで \(s\) と \(t\) は \(V\) に属さない新しいオブジェクトを表す。

  任意の頂点 \(p \in V\) に対して、頂点 \(p^{\prime}\in V^{\prime}\) を次のように定める:

  \[ p^{\prime}= \begin{cases} s & (p\in X \text{ のとき})\\ t & (p\in Y \text{ のとき})\\ p & (\text{それ以外のとき}) \end{cases} \]

  この頂点 \(p^{\prime}\) を \(p\) の射影 (projection) と呼ぶ。

• \(D\) の弧は全てそのままとする。ただし、弧の端点 (始点と終点) はその射影で置き換える (つまり、\(X\) に属する端点は \(s\) で置き換え、\(Y\) に属する端点は \(t\) で置き換え、\(X\) にも \(Y\) にも属さない端点はそのままとする)。例えば、\(X\) に属する始点を持つ弧は \(s\) を始点に持つ弧になる。形式的に表現すると次のようになる: \(A^{\prime}=A\) と定め、\(\psi^{\prime}\colon A^{\prime}\rightarrow V^{\prime}\times V^{\prime}\) を次のように定める: 任意の \(a \in A^{\prime}=A\) に対して \(\left( u,v\right) =\psi\left( a\right) \) を満たす \(u\), \(v\) を用いて \(\psi^{\prime}\left( a\right) =\left( u^{\prime},v^{\prime}\right) \) と定める。

例えば、例 10.1.19 の多重有向グラフを \(D\) とするとき、\(D^{\prime}\) は次の多重有向グラフとなる:

定理 10.1.10 を \(D^{\prime}=\left( V^{\prime },A^{\prime},\psi^{\prime}\right) \) に適用すると、\(D^{\prime}\) における \(s\) から \(t\) への路からなる任意の二要素が弧素な集合の最大要素数が \(D^{\prime}\) の \(s\)-\(t\)-カットの最小要素数に等しいと分かる。

この事実を使って示すべき命題を証明しよう。\(D^{\prime}\) の \(s\)-\(t\)-カットの最小要素数が \(D\) の \(X\)-\(Y\)-カットの最小要素数に等しいことは容易に分かる (実際、\(D^{\prime}\) の \(s\)-\(t\)-カットは \(D\) の \(X\)-\(Y\)-カットでもある⁹)。\(D^{\prime}\) における \(s\) から \(t\) への路からなる任意の二要素が弧素な集合の最大要素数が \(D\) における \(X\) から \(Y\) への路からなる任意の二要素が弧素な集合の最大要素数と等しいと示せれば、前段落の事実から定理 10.1.18 が証明される。

では、\(D^{\prime}\) における \(s\) から \(t\) への路からなる任意の二要素が弧素な集合の最大要素数が \(D\) における \(X\) から \(Y\) への路からなる任意の二要素が弧素な集合の最大要素数と等しいと示すには、どうすればいいだろうか？ 二つの集合の間に全単射があればすぐに示せるものの、全単射の存在は自明でない: \(D^{\prime}\) の同じ頂点に射影される \(D\) の頂点が存在するので、\(D\) における \(X\) から \(Y\) への路に含まれる頂点をその射影に置き換えると、得られるのは \(D^{\prime}\) における \(s\) から \(t\) への歩道となる。

幸い、これは簡単に修正できる。\(D\) における \(X\) から \(Y\) への路からなる任意の二要素が弧素な \(k\) 要素集合が存在すると仮定する。このとき、それぞれの路に含まれる頂点をその射影と置き換えることで、\(D^{\prime}\) における \(s\) から \(t\) への歩道からなる任意の二要素が弧素な \(k\) 要素集合を構築できる。さらに、その集合に含まれる歩道をそれが含む路に置き換えると、\(s\) から \(t\) への路からなる任意の二要素が弧素な \(k\) 要素集合が得られる (命題 4.5.8 の証明から分かるように、任意の \(s\) から \(t\) への歩道は \(s\) から \(t\) への路を含む)。よって次の不等式を得る:

逆に、\(D^{\prime}\) における \(s\) から \(t\) への路からなる任意の二要素が弧素な \(k\) 要素集合が存在すると仮定する。この集合に含まれる \(k\) 個の路を\(D\) の路に「引き上げる」(弧はそのままにして、頂点 \(s\), \(t\) をそれぞれ弧と矛盾しない \(X\), \(Y\) に属する頂点に置き換える) ことで、\(D\) における \(X\) から \(Y\) への路からなる任意の二要素が弧素な \(k\) 要素集合が得られる。よって次の不等式を得る:

二つの不等式より次の等式が分かる:

先述したように、これで定理 10.1.18 は証明された。□

10.1.2無向グラフの辺に関する Menger の定理

これから定理 10.1.6 と定理 10.1.10 の無向グラフバージョンと言える命題を示す。面白くない定義が最初にある:

定理 10.1.6 には次の命題が対応する:

定理 10.1.10 の無向グラフバージョンを表明するには、定義 10.1.8 に対応する次の定義が必要になる:

次の Remark は Remark 10.1.9 に対応する:

[証明] Remark 10.1.9 と同様に示せる。□

次の定理は定理 10.1.10 の無向グラフバージョンである:

[証明] 何もないところから証明を組み立てることはせず、有向グラフに対する同様の命題 (定理 10.1.10) を使って証明する。

具体的には、定理 10.1.10 を \(D=G^{\operatorname*{bidir}}\) に適用する¹⁰。ここから、\(G^{\operatorname*{bidir}}\) における \(s\) から \(t\) への路からなる任意の二要素が弧素な集合の最大要素数は、\(G^{\operatorname*{bidir}}\) の \(s\)-\(t\)-カットの最小要素数に等しいと分かる。 これは示したい命題に似ているものの、同じではない: \(G^{\operatorname*{bidir}}\) と \(G\) は異なる。示したい命題を得るには、次の二つの命題を証明する必要がある:

Claim 2 は簡単に確かめられる: \(G^{\operatorname*{bidir}}\) の有向 \(s\)-\(t\)-カットは \(G\) の無向 \(s\)-\(t\)-カットに本質的に等しい¹²。

後は Claim 1 を確かめればよい。最も単純なアプローチは \(G^{\operatorname*{bidir}}\) における \(s\) から \(t\) への路を (路に含まれる弧を対応する無向辺に置き換えることで) \(G\) における \(s\) から \(t\) への路に変換できると論じるものである。しかし、この議論は正しくない: この変換方法では、\(G^{\operatorname*{bidir}}\) で弧素な二つの路から得られる \(G\) における二つの路が辺素にならない可能性がある。この例を次に示す。\(u\) と \(v\) の間にある二つの弧は \(G\) で一つの辺となるものの、\(G^{\operatorname*{bidir}}\) では赤と青の二つの路によって利用されている:

この図で赤と青が表す二つの路に含まれる弧を辺に置き換えると、辺素でない二つの路が得られる (\(u\) と \(v\) を端点に持つ辺が両方の路によって使われるため)。

しかし、この種の状況を回避する方法がある。\(G^{\operatorname*{bidir}}\) における \(s\) から \(t\) への路からなる任意の二要素が弧素な集合の最大要素数を \(k\) とする。その上で、\(G^{\operatorname*{bidir}}\) における \(s\) から \(t\) への路からなる任意の二要素が弧素な \(k\) 要素集合 \(\{\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{k}\}\) を、全長が最小になるように取る (路の集合の全長とは \(\mathbf{p}_{1},\mathbf{p}_{2},\ldots ,\mathbf{p}_{k}\) の長さの和を意味する)。このとき、\(\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{k}\) の弧を辺に置き換えて得られる \(k\) 個の \(G\) における路は任意の二つが辺素となることが容易に示せる。

[証明: 背理法で示す。\(\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{k}\) の弧を辺に置き換えたとき、二つの路 \(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) に対応する \(G\) の路が辺素でないとする (\(i \neq j\))。変換後の二つの路に共通する辺を \(e\) とする。\(e\) の端点を \(\mathbf{p}_{i}\) が通る順番で \(u\), \(v\) とする。このとき \(\mathbf{p}_{i}\) は \(e\) を (正確には、\(e\) に対応する \(G^{\operatorname*{bidir}}\) の二つの弧の一つを) \(u\) から \(v\) へ通り抜ける。

二つの路 \(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) は弧素だから、辺 \(e\) を同じ方向に通り抜けることはない。よって \(\mathbf{p}_{j}\) は辺 \(e\) を \(v\) から \(u\) に (\(\mathbf{p}_{i}\) と逆方向に) 通り抜ける。つまり \(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) は次の形をしている:

ここで \(e_{1}\) と \(e_{2}\) は \(e\) に対応する \(G^{\operatorname*{bidir}}\) の二つの弧を表す。この二つの路 \(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) から次の二つの歩道を新しく構築できる¹³:

これらの歩道 \(\mathbf{p}_{i}^{\prime}\) と \(\mathbf{p}_{j}^{\prime}\) はどちらも \(s\) から \(t\) への歩道であり、元々 \(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) が使っていた弧だけを含む。よって \(\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{k}\) の \(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) 以外の任意の路と \(\mathbf{p}_{i}^{\prime}\) および \(\mathbf{p}_{j}^{\prime}\) は弧素である。さらに、\(\mathbf{p}_{i}^{\prime}\) と \(\mathbf{p}_{j}^{\prime}\) も弧素である (\(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) が弧素であり、路である \(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) には同じ弧が含まれないため)。また、\(\mathbf{p}_{i}^{\prime}\) と \(\mathbf{p}_{j}^{\prime}\) の長さの和は \(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) の長さの和より \(2\) だけ小さい (\(e_{1}\) と \(e_{2}\) が使われなくなるため)。\(\mathbf{p}_{i}^{\prime}\) と \(\mathbf{p}_{j}^{\prime}\) が路とは限らないものの、(命題 4.5.8 の証明と同様に) 閉路を繰り返し除去することで路にできる。この操作を行うと、\(s\) から \(t\) への二つの路 \(\mathbf{p}_{i}^{\prime\prime}\), \(\mathbf{p}_{j}^{\prime\prime}\) が得られる。\(\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{k}\) の \(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) 以外の任意の路と \(\mathbf{p}_{i}^{\prime\prime}\) および \(\mathbf{p}_{j}^{\prime\prime}\) は弧素であり、\(\mathbf{p}_{i}^{\prime\prime}\) と \(\mathbf{p}_{j}^{\prime\prime}\) も弧素であり、\(\mathbf{p}_{i}^{\prime\prime}\) と \(\mathbf{p}_{j}^{\prime\prime}\) の長さの和は \(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) の長さの和より \(2\) 以上小さい。

よって、\(\{\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{k}\}\) の \(\mathbf{p}_{i}\) と \(\mathbf{p}_{j}\) を \(\mathbf{p}_{i}^{\prime\prime}\) と \(\mathbf{p}_{j}^{\prime\prime}\) に入れ替えれば、\(s\) から \(t\) への路からなる任意の二要素が弧素な \(k\) 要素集合であって全長が \(\{\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{k}\}\) より小さいものが得られる。しかしこれは、\(s\) から \(t\) への路からなる任意の二要素が弧素な \(k\) 要素集合であって全長が最小のものが \(\{\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{k}\}\) である事実と矛盾する。この矛盾は仮定が偽であることを示す。つまり路 \(\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{k}\) の弧を辺に置き換えて得られる \(k\) 個の \(G\) の路は任意の二つが辺素である。]

これで \(G\) における \(s\) から \(t\) への路からなる任意の二要素が辺素な \(k\) 要素集合 (\(\{\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{k}\}\) の弧を辺に置き換えたもの) が見つかった。よって \(k\) の定義より次の不等式を得る:

逆に、次の不等式は容易に分かる:

[\(G\) の路に含まれる各辺を対応する二つの \(G^{\operatorname*{bidir}}\) の弧の向きが正しい方に置き換えることで、\(G\) の路を \(G^{\operatorname*{bidir}}\) の路に変換できる。このとき \(G\) で弧素な二つの路からは \(G^{\operatorname*{bidir}}\) で弧素な二つの路が得られるため。] よって次の等式を得る:

これで Claim 1 が示せた。先述したように、以上で定理 10.1.25 は証明された。□

[定理 10.1.22 の証明] 定理 10.1.10 と Remark 10.1.9 から定理 10.1.6 を示したのと同様の議論を使うことで、定理 10.1.25 と Remark 10.1.24 から示せる。□

10.1.3有向グラフの頂点に関する Menger の定理

これまでに示した Menger の定理は共通の弧 (または辺) を持たない路からなる集合を考えてきた。共通の頂点を避けたい場合には何が言えるだろうか？

例 10.1.28

例 10.1.2 の二つの路 \(\mathbf{p}\) と \(\mathbf{q}\) は弧素であるものの、内部頂点素ではない。

内部頂点素な二つの路 \(\mathbf{p}\) と \(\mathbf{q}\) の例を次に示す:

内部頂点素な路に関する自明なケースとして、長さが \(1\) 以下の路がある。つまり、長さが \(1\) 以下の路は自身を含む任意の路と内部頂点素となる (そもそも内部頂点を持たないため)。

例 10.1.30

\(D=\left( V,A,\psi\right) \) を次の多重有向グラフとする:

このとき、集合 \(\left\{ a,b\right\} \) と \(\left\{ a,c\right\} \) はいずれも \(s\)-\(t\)-内部頂点切断である。実際、頂点 \(a\), \(b\) または頂点 \(a\), \(c\) を除去すると \(s\) と \(t\) が切り離される。これに対して、集合 \(\left\{ a\right\} \) と \(\left\{ b,c\right\} \) はいずれも \(s\)-\(t\)-内部頂点切断でない。実際、\(c\) と \(b\) を経由する \(s\) から \(t\) への路は \(a\) を含まず、\(a\) を経由する \(s\) から \(t\) への路は \(b\) と \(c\) を含まない。

続いて、内部頂点素な路に関する定理 10.1.6 と定理 10.1.10 を表明する:

例 10.1.33

\(D\) を次の多重有向グラフとする:

このとき、\(s\) から \(t\) への路からなる任意の二要素が内部頂点素な集合の最大要素数は \(2\) である。実際、次の図に赤と青で示された二つの路は内部頂点素である:

任意の二つが内部頂点素な \(3\) つの路は存在するだろうか？ 一見しただけでは明らかでないものの、定理 10.1.32 を使うと簡単に分かる。定理 10.1.32 より、\(s\) から \(t\) への路からなる任意の二要素が内部頂点素な集合の最大要素数は \(s\)-\(t\)-内部頂点切断の最小要素数に等しい。よって、前者の値が \(2\) より大きいなら、後者の値も \(2\) より大きくなる。しかし、容易に確認できるように \(2\) 要素集合 \(\left\{ a,f\right\} \) は \(s\)-\(t\)-内部頂点切断だから、両方の値は \(2\) である。

[定理 10.1.32 の証明] ここでも有向グラフの弧に関する Menger の定理 (定理 10.1.10) を適切な有向グラフ \(D^{\prime}=\left( V^{\prime},A^{\prime},\psi^{\prime}\right) \) に適用する。

多重有向グラフ \(D^{\prime}\) はどんなグラフだろうか？ 有向グラフ \(D\) を改変し、共通の内部頂点を持つ \(D\) の路が \(D^{\prime}\) で共通の弧を持つようにすることが基本的なアイデアとなる。最も自然な方法は次の通りである: \(D\) の各頂点 \(v\) を二つに「引きちぎる」ことで \(v^{i}\) と \(v^{o}\) という二つの頂点に置き換え、さらに始点 \(v^{i}\) と終点 \(v^{o}\) を持つ弧 \(v^{io}\) を追加する (\(v^{i}\) と \(v^{o}\) はそれぞれ「\(v\)-in」と「\(v\)-out」を表す。\(v^{i}\) は \(v\) への「入口」、\(v^{o}\) は \(v\) からの「出口」と解釈できる)。もともと \(D\) に存在する任意の弧 \(a\) は \(D^{\prime}\) で弧 \(a^{oi}\) となり、弧 \(a\) が始点 \(u\) と終点 \(v\) を持つとき弧 \(a^{oi}\) は始点 \(u^{o}\) と終点 \(v^{i}\) を持つ。

例を次に示す。\(D=\left( V,A,\psi\right) \) を次の多重有向グラフとする:

このとき \(D^{\prime}\) は次の多重有向グラフとなる:

[\(a \in A\) に対応する \(a^{oi}\) の形をした弧は青で、その他の \(v^{io}\) の形をした弧は赤で示されている。] この \(D^{\prime}\) は所望の性質を持つ: 例えば、次に示す二つの \(D\) の路は共通の頂点 \(y\) を持つ:

この二つの路に対応する \(D^{\prime}\) の路を次に示す:

この二つの路は確かに共通の弧 \(y^{io}\) を持つ。頂点が乗り換え駅、弧が駅間の接続関係を表す鉄道ネットワークが \(D\) だと考えれば、\(D^{\prime}\) は乗り換えを表す弧を持った詳細な鉄道ネットワークと考えることができる。

この多重有向グラフ \(D^{\prime}=\left( V^{\prime },A^{\prime},\psi^{\prime}\right) \) の最大限に一般化した形式的な定義を示す:

• \(D\) の各頂点 \(v\) は \(D^{\prime}\) で二つの新しい頂点 \(v^{i}\) と \(v^{o}\) に置き換わる。\(v^{i}\) を入頂点 (in-vertex) と呼び、\(v^{o}\) を出頂点 (out-vertex) と呼ぶ。\(D^{\prime}\) の頂点集合 \(V^{\prime}\) は次のように定義される:

  \[ V^{\prime}\colonequals \underbrace{\left\{ v^{i}\mid v\in V\right\} }_{\text{入頂点}}\cup\underbrace{\left\{ v^{o}\mid v\in V\right\}}_{\text{出頂点}} \]

• \(D\) の各弧 \(a \in A\) は \(D^{\prime}\) で新しい弧 \(a^{oi}\) に置き換わる。弧 \(a \in A\) が始点 \(u\) と終点 \(v\) を持つとき、\(a\) は始点 \(u^{o}\) と終点 \(v^{i}\) を持つ新しい弧 \(a^{oi}\) に置き換わる。この \(a^{oi}\) を \(D^{\prime}\) の弧弧 (arc-arc) と呼ぶ (\(D\) の弧から生まれた弧であるため)。

• \(D\) の各頂点 \(v \in V\) ごとに、始点 \(v^{i}\) と終点 \(v^{o}\) を持つ新しい弧 \(v^{io}\) が \(D^{\prime}\) に追加される。この弧 \(v^{io}\) を \(D^{\prime}\) の頂点弧 (vertex-arc) と呼ぶ (\(D\) の頂点から生まれた弧であるため)。

• \(D^{\prime}\) の弧集合 \(A^{\prime}\) は次のように定義される:

  \[ A^{\prime}\colonequals \underbrace{\left\{ a^{oi}\mid a\in A\right\} }_{\text{弧弧}}\cup\underbrace{\left\{ v^{io}\mid v\in V\right\} }_{\text{頂点弧}} \]

  写像 \(\psi^{\prime}\colon A^{\prime}\rightarrow V^{\prime}\times V^{\prime}\) の定義はこれまでに説明した通りである:

  • 任意の弧弧 \(a^{oi} \in A^{\prime}\) に対しては \(\psi^{\prime}\left( a^{oi}\right) \colonequals \left( u^{o},v^{i}\right) \) と定義される。ここで \(\left( u,v\right) =\psi\left( a\right) \) である。

  • 任意の頂点弧 \(v^{io} \in A^{\prime}\) に対しては \(\psi^{\prime}\left( v^{io}\right) \colonequals \left( v^{i},v^{o}\right) \) と定義される。

\(D^{\prime}\) は「二部有向グラフ」とでも言えるグラフであることに注目してほしい: \(D^{\prime}\) の弧はどれも出頂点と入頂点を接続する。つまり、弧弧は出頂点から入頂点への弧であり、頂点弧は入頂点から出頂点への弧である。ここから、\(D^{\prime}\) の任意の歩道は弧弧と頂点弧を交互に使うことが分かる。

\(\mathbf{p}=\left( v_{0},a_{1},v_{1},a_{2},v_{2},\ldots,a_{k},v_{k}\right) \) を非自明な¹⁴ \(D\) の路とするとき、対応する \(D^{\prime}\) の路 \(\mathbf{p}^{oi}\) を次のように定義できる:

この路 \(\mathbf{p}^{oi}\) は \(\mathbf{p}\) から次の操作で構築できる:

• 始点 \(v_{0}\) を \(v_{0}^{o}\) に置き換える。

• 終点 \(v_{k}\) を \(v_{k}^{i}\) で置き換える。

• その他の任意の頂点 \(v_{j}\) を列 \(v_{j}^{i},v_{j}^{io},v_{j}^{o}\) で置き換える。

• 任意の弧 \(a_{j}\) を \(a_{j}^{oi}\) で置き換える。

形式的でない言い方をすれば、\(\mathbf{p}\) の全ての内部頂点を二つに引きちぎった上で対応する頂点弧を間に入れると \(\mathbf{p}^{oi}\) が得られる。

\(\mathbf{p}\) が \(D\) における \(s\) から \(t\) への路なら、\(\mathbf{p}^{oi}\) は \(D^{\prime}\) における \(s^{o}\) から \(t^{i}\) への路となる。逆に、\(D^{\prime}\) における \(s^{o}\) から \(t^{i}\) への任意の路は、\(D\) における \(s\) から \(t\) への路を使って \(\mathbf{p}^{oi}\) と書ける (\(D^{\prime}\) の任意の歩道は弧弧と頂点弧を交互に使うため)。よって次の写像 \(f\) は全単射である:

さらに、\(D\) における二つの路 \(\mathbf{p}\) と \(\mathbf{q}\) が内部頂点素となるのは、\(D^{\prime}\) における二つの路 \(\mathbf{p}^{oi}\) と \(\mathbf{q}^{oi}\) が弧素となるとき、かつそのときに限る (路 \(\mathbf{p}\) の始点と終点を除く各頂点に対応する弧が \(\mathbf{p}^{oi}\) に存在するため)。

\(D^{\prime}\) における \(s^{o}\) から \(t^{i}\) への路からなる任意の二要素が弧素な集合の最大要素数を \(k\) とする。この条件を満たす \(k\) 要素集合に \(f\) の逆写像を適用すれば、\(D\) における \(s\) から \(t\) への路からなる任意の二要素が内部頂点素な \(k\) 要素集合が得られる (前段落で示した事実より)。よって次の不等式が分かる:

続いて、要素数が \(k\) 以下の \(s\)-\(t\)-内部頂点切断 \(W\subseteq V\setminus\left\{ s,t\right\} \) を見つけることが目標となる。このために、まず設定を単純化する。

\(s\) から \(t\) への路はループを含まない。また、始点 \(t\) と終点 \(s\) を持つ弧も含まない (路の頂点は相異なる必要があるため)。よって、それらを除去しても問題ない。つまり、今考えている定理 10.1.32 を証明する上では、ループおよび始点 \(t\) と終点 \(s\) を持つ弧を \(D\) から除去しても問題ない。よって有向グラフ \(D\) はそういった弧を持たないと一般性を失うことなく仮定する。定理の仮定より \(D\) は始点 \(s\) と終点 \(t\) を持つ弧を持たないので、このとき \(D\) は \(\left\{ s,t\right\} \) に属する始点と \(\left\{ s,t\right\} \) に属する終点を持つ弧を持たない (そういった弧は始点 \(t\) と終点 \(s\) を持つか、始点 \(s\) と終点 \(t\) を持つか、ループであるため)。言い換えれば、\(D\) の任意の弧は \(s\) でも \(t\) でもない端点¹⁵を少なくとも一つ持つ。

一方、\(D^{\prime}\) における \(s^{o}\) から \(t^{i}\) への路からなる任意の二要素が弧素な集合の最大要素数が \(k\) だから、定理 10.1.10 を \(D^{\prime}=\left( V^{\prime},A^{\prime},\psi^{\prime}\right) \) と \(s^{o}\), \(t^{i}\) に適用すると、\(D^{\prime}\) の \(s^{o}\)-\(t^{i}\)-カットの最小要素数も \(k\) だと分かる。つまり \(\left\vert \left[ S,\overline{S}\right] \right\vert =k\) を満たす \(D^{\prime}\) の \(s^{o}\)-\(t^{i}\)-カット \(\left[ S,\overline{S}\right] \) が存在する。\(\left[ S,\overline{S}\right] \) が \(s^{o}\)-\(t^{i}\)-カットなので、\(s^{o}\in S\) と \(t^{i}\notin S\) と \(S\subseteq V^{\prime}\) が成り立つ。

\(B\colonequals \left[ S,\overline{S}\right] \) と定める。このとき \(\left\vert B\right\vert =\left\vert \left[ S,\overline{S}\right] \right\vert =k\) である。さらに \(s^{io}\notin B\)¹⁶ と \(t^{io} \notin B\)¹⁷ も容易に分かる。

\(D^{\prime}\) の任意の頂点 \(w\in V^{\prime}\) に対して、\(D\) の頂点 \(\beta\left( w\right) \in V\) を次のように割り当てる: \(w\) は \(D^{\prime}\) の頂点より \(w=v^{i}\) または \(w=v^{o}\) を満たす頂点 \(v\) が存在するから、\(\beta\left( w\right) \colonequals v\) と定める。言い換えれば、\(\beta\left( w\right) \) は \(w\in\left\{ v^{i},v^{o}\right\} \) を満たす頂点 \(v\) である。この \(\beta\left( w\right) \) を頂点 \(w\) の基頂点 (base vertex) と呼ぶ。

任意の弧 \(b \in B\) に対して、\(b\) の少なくとも一つの端点 \(w\) は \(\beta\left( w\right) \in V\setminus\left\{ s,t\right\} \) を満たす¹⁸。この条件を満たす端点 \(w\) を任意に取り、その基頂点 \(\beta\left( w\right) \) を \(\beta\left( b\right) \) と表記する。この \(\beta\left( b\right) \) を弧 \(b\) の基頂点 (base point) と呼ぶ。定義より次が分かる:

さらに、集合 \(\left\{ \beta\left( b\right) \mid b\in B\right\} \) を \(\beta\left( B\right) \) と表記する。明らかに \(\left\vert \beta\left( B\right) \right\vert \leq\left\vert B\right\vert =k\) である。

これから次の命題を証明する:

[証明: \(D\) における \(s\) から \(t\) への路を任意に取って \(\mathbf{p}\) とする。\(\mathbf{p}\) が \(\beta\left( B\right) \) に属する頂点を含むと示せばよい。

\(D\) の路 \(\mathbf{p}\) に対して \(D^{\prime}\) の路 \(\mathbf{p}^{oi}\) を割り当てたことを思い出してほしい。\(\mathbf{p}^{oi}\) の定義より、\(\mathbf{p}^{oi}\) の任意の頂点に対応する基頂点は \(\mathbf{p}\) の頂点だと分かる (実際、\(\mathbf{p}\) の頂点が \(v_{0}\), \(v_{1}\), ..., \(v_{k}\) なら \(\mathbf{p}^{oi}\) の頂点は \(v_{0}^{o}\), \(v_{1}^{i}\), \(v_{1}^{o}\), \(v_{2}^{i}\), \(v_{2}^{o}\), ..., \(v_{k-1}^{i}\), \(v_{k-1}^{o}\), \(v_{k}^{i}\) であり、それらの基頂点は \(v_{0}\), \(v_{1}\), \(v_{1}\), \(v_{2}\), \(v_{2}\), ..., \(v_{k-1}\), \(v_{k-1}\), \(v_{k}\) である)。

\(\mathbf{p}\) は \(s\) から \(t\) への路なので、\(\mathbf{p}^{oi}\) は \(s^{o}\) から \(t^{i}\) への路である。よって \(\mathbf{p}^{oi}\) は \(S\) に属する頂点から始まって \(S\) に属さない頂点で終わる (\(s^{o} \in S\) と \(t^{i}\notin S\) より)。よって路 \(\mathbf{p}^{oi}\) はどこかで \(S\) から \(\overline{S}\) に移動する。言い換えれば、\(\mathbf{p}^{oi}\) の弧 \(b\) であって始点が \(S\) に含まれ終点が \(\overline{S}\) に含まれるものが存在する。この \(b\) は \(b\in\left[ S,\overline{S}\right] =B\) を満たすから、\(\beta\left( B\right) \) の定義より \(\beta\left( b\right) \in\beta\left( B\right) \) が成り立つ。また、\(\mathbf{p}^{oi}\) の弧である \(b\) の両端点は \(\mathbf{p}^{oi}\) の頂点である。

この弧 \(b\) の基頂点 \(\beta\left( b\right) \) に注目する。\(\beta\left( b\right) \) の定義より、\(\beta\left( b\right) \) は \(b\) の端点の基頂点である。\(b\) の両端点は \(\mathbf{p}^{oi}\) の頂点だから、\(\beta\left( b\right) \) は \(\mathbf{p}^{oi}\) の頂点の基頂点だと分かる。つまり \(\beta\left( b\right) \) は \(\mathbf{p}\) の頂点である (先述したように、\(\mathbf{p}^{oi}\) の頂点の基頂点は \(\mathbf{p}\) の頂点であるため)。言い換えれば、路 \(\mathbf{p}\) は頂点 \(\beta\left( b\right) \) を含む。\(\beta\left( b\right) \in\beta\left( B\right) \) だったから、\(\mathbf{p}\) は頂点 \(\beta\left( B\right) \) に属する頂点を含むと結論できる。以上で命題 \((2)\) は証明された。]

任意の \(b\in B\) に対して \(\beta\left( b\right) \in V\setminus\left\{ s,t\right\} \) だから、集合 \(\beta\left( B\right) \) は \(V\setminus\left\{ s,t\right\} \) の部分集合である。さらに命題 \((2)\) より、\(s\) から \(t\) への任意の路は \(\beta\left( B\right) \) に属する頂点を含む。言い換えれば、\(\beta\left( B\right) \) は \(s\) から \(t\) への任意の路が \(W\) に属する頂点を含むような部分集合 \(W\subseteq V\setminus\left\{ s,t\right\} \) である。\(s\)-\(t\)-内部頂点切断の定義より、\(\beta\left( B\right) \) は \(s\)-\(t\)-内部頂点切断だと分かる。さらに式 \((1)\) より次の不等式が分かる:

一方で、鳩ノ巣原理より¹⁹次の不等式が分かる:

二つの不等式を組み合わせれば次の等式を得る:

以上で定理 10.1.32 は証明された。□

有向グラフの弧に関する Menger の定理に多終端バージョン (定理 10.1.18) が存在したのと同じように、有向グラフの頂点に関する Menger の定理にも多終端バージョンが存在する。それを表明するには、ここでも定義がいくつか必要になる:

例 10.1.37

多重有向グラフ \(D\) および \(D\) の頂点集合の部分集合 \(X\), \(Y\) を次のように定める:

このとき、\(X\) から \(Y\) への路からなる任意の二要素が内部頂点素な集合の最大要素数は \(2\) である。実際、次の図に赤と青で示す内部頂点素な二つの路が存在する:

[もちろん他の選択肢もある。] \(X\)-\(Y\)-内部頂点切断の最小要素数も \(2\) である。実際、\(2\) 要素の \(X\)-\(Y\)-内部頂点切断として集合 \(\left\{ a,b\right\} \) がある。定理 10.1.36 が主張するように、二つの値は確かに等しい。

[定理 10.1.36 の証明] 定理 10.1.18 と同様の方法で新しい多重有向グラフ \(D^{\prime}=\left( V^{\prime},A^{\prime},\psi^{\prime}\right) \) を構築する。\(X\) に属する始点と \(Y\) に属する終点を持つ弧が \(D\) に存在しないので、\(D^{\prime}\) には始点 \(s\) と終点 \(t\) を持つ弧が存在しない。

よって定理 10.1.32 を \(D^{\prime}=\left( V^{\prime },A^{\prime},\psi^{\prime}\right) \) に適用すれば、\(D^{\prime}\) における \(s\) から \(t\) への路からなる任意の二要素が内部頂点素な集合の最大要素数が \(D^{\prime}\) の \(s\)-\(t\)-内部頂点切断の最小要素数に等しいと分かる。

この結果が元の \(D\) に関して何を示すかを考えよう:

• \(D^{\prime}\) の \(s\)-\(t\)-内部頂点切断の最小要素数は、\(D\) の \(X\)-\(Y\)-内部頂点切断の最小要素数に等しい (実際、\(D^{\prime}\) の \(s\)-\(t\)-内部頂点切断は全て \(D\) の \(X\)-\(Y\)-内部頂点切断でもある²⁰)。

• \(D^{\prime}\) における \(s\) から \(t\) への路からなる任意の二要素が内部頂点素な集合の最大要素数は、\(D\) における \(X\) から \(Y\) への路からなる任意の二要素が内部頂点素な集合の最大要素数に等しい²¹。

よって前段落の結果は定理 10.1.36 に等しく、これで証明は完了した。□

この定理には (内部頂点素ではなく) 頂点素な路という概念を利用する別バージョンがある。こちらの方が定義は単純になる:

例 10.1.40

有向グラフ \(D\) および \(D\) の頂点集合の部分集合 \(X\), \(Y\) を次のように定める:

このとき、\(X\) から \(Y\) への路からなる任意の二要素が頂点素な集合の最大要素数は \(2\) である。実際、次の図に赤と青で示す頂点素な二つの路が存在する:

もし任意の二要素が内部頂点素な路の集合を考えているなら、さらにもう一つ路 (具体的には、\(X\) の一番上の頂点から始まって \(Y\) の一番上の頂点で終わる路) を取ることができる。しかし、この路と赤い路は内部頂点素ではあるものの頂点素ではない。少し考えれば、\(X\) から \(Y\) への路からなる任意の二要素が頂点素な集合の最大要素数が \(2\) であることが分かる。

\(X\)-\(Y\)-頂点切断の最小要素数も \(2\) である。実際、要素数 \(2\) の \(X\)-\(Y\)-頂点切断として \(\left\{ u,y\right\} \) がある。定理 10.1.39 が主張するように、この値は \(X\) から \(Y\) への路からなる任意の二要素が頂点素な集合の最大要素数に等しい。

[定理 10.1.39 の証明] 示すべき命題を定理 10.1.32 に帰着させる。ここでも有向グラフを適切に変更するアプローチを用いるが、施す変更は非常に単純である: 二つの新しい頂点 \(s\), \(t\) を \(D\) に追加し、\(s\) から全ての \(x\in X\) への弧および全ての \(y\in Y\) から \(t\) への弧を追加する (全部で \(\left\vert X\right\vert +\left\vert Y\right\vert \) 本の新しい弧が追加される)。こうして得られる多重有向グラフを \(D^{\prime}\) とする。詳しく言えば、\(D^{\prime}\) の定義は次の通りである:

• 新しい頂点 \(s\) と \(t\) を作成し、\(V^{\prime}\colonequals V\cup\left\{ s,t\right\} \) と定める。この集合 \(V^{\prime}\) は \(D^{\prime}\) の頂点集合となる。

• 頂点 \(x\in X\) ごとに新しい弧 \(a_{x}\) を作成する。弧 \(a_{x}\) は始点 \(s\) と終点 \(x\) を持つ。

• 頂点 \(y \in Y\) ごとに新しい弧 \(b_{y}\) を作成する。弧 \(b_{y}\) は始点 \(y\) と終点 \(t\) を持つ。

• \(a_{x}\) と \(b_{y}\) を使って \(A^{\prime}\colonequals A\cup\left\{ a_{x}\mid x\in X\right\} \cup\left\{ b_{y}\mid y\in Y\right\} \) と定める。この集合 \(A^{\prime}\) は \(D^{\prime}\) の弧集合となる。

• 写像 \(\psi\colon A\rightarrow V\times V\) を次のように拡張して写像 \(\psi^{\prime }\colon A^{\prime}\rightarrow V^{\prime}\times V^{\prime}\) を定める:

  \[ \begin{alignedat}{3} & \psi^{\prime}\left( a_{x}\right) && = \left( s,x\right) \quad & (\forall x \in X) \\ & \psi^{\prime}\left( b_{y}\right) && = \left( y,t\right) \quad & (\forall y \in Y) \\ & \psi^{\prime}\left( c\right) && =\psi\left( c\right) \quad & (\forall c \in A) \end{alignedat} \]

• 多重有向グラフ \(\left( V^{\prime },A^{\prime},\psi^{\prime}\right) \) を \(D^{\prime}\) と定める。

例えば、\(D\) が例 10.1.40 の多重有向グラフなら、\(D^{\prime}\) は次の多重有向グラフとなる:

弧 \(a_{x}\) は赤で、弧 \(b_{y}\) は青で描かれている。

\(D^{\prime}\) の構成より、\(D^{\prime}\) は始点 \(s\) と終点 \(t\) を持つ弧を持たない。よって \(D^{\prime }=\left( V^{\prime},A^{\prime},\psi^{\prime}\right) \) には定理 10.1.32 を適用できる。よって \(s\) から \(t\) への路からなる任意の二頂点が内部頂点素な集合の最大要素数は \(s\)-\(t\)-内部頂点切断の最小要素数に等しい。一方で、次の二つの命題は容易に分かる:

[命題 1 の証明の概要: \(D^{\prime}\) における \(s\) から \(t\) への任意の路を \(\mathbf{p}\) とする。\(\mathbf{p}\) の始点と終点を除去すると、\(D\) における \(X\) から \(Y\) への路が得られる。この路を \(\overline{\mathbf{p}}\) とする。この操作は次の写像を定める:

容易に分かるように、この写像は全単射である (実際、\(X\) から \(Y\) への路 \(\mathbf{q}\) が与えらたとき、先頭に \(s\) と適切な \(a_{x}\) を、末尾に適切な \(b_{y}\) と \(t\) を \(\mathbf{q}\) に追加することで \(s\) から \(t\) への路 \(\mathbf{p}\) を構築でき、この \(\mathbf{p}\) は \(\overline{\mathbf{p}} = \mathbf{q}\) を満たす)。さらに、\(s\) から \(t\) への二つの路 \(\mathbf{p}\) と \(\mathbf{q}\) が内部頂点素となるのは、対応する路 \(\overline{\mathbf{p}}\) と \(\overline{\mathbf{q}}\) が頂点素なとき、かつそのときに限る (\(\mathbf{p}\) の内部頂点は \(\overline{\mathbf{p}}\) の頂点であり、\(\mathbf{q}\) の内部頂点は \(\overline{\mathbf{q}}\) の頂点であるため)。ここから命題 1 が証明される。]

[命題 2 の証明の概要: \(D^{\prime}\) の \(s\)-\(t\)-内部頂点切断と \(D\) の \(X\)-\(Y\)-頂点切断が等しいことは容易に分かる (これを示すには、命題 1 で言及した全単射と \(V^{\prime}\setminus\left\{ s,t\right\} =V\) を使って二つの概念の定義を比較する)。ここから命題 2 が証明される。]

\(s\) から \(t\) への路からなる任意の二頂点が内部頂点素な集合の最大要素数は \(s\)-\(t\)-内部頂点切断の最小要素数に等しいので、命題 1 と命題 2 より次が分かる: \(X\) から \(Y\) への路からなる任意の二要素が頂点素な集合の最大要素数は \(X\)-\(Y\)-頂点切断の最小要素数に等しい。以上で定理 10.1.39 は証明された。□

なお、Hall の結婚定理 (定理 8.3.4) は有向グラフに関する Menger の定理のどれを使っても容易に証明できる [練習問題！]。逆方向の証明も可能だと聞いたことがある。このため、Menger の定理は Hall の結婚定理と同値な定理群 (König の定理など) に含まれると言える。

10.1.4無向グラフの頂点に関する Menger の定理

無向グラフの頂点に関する Menger の定理も存在する。定理 10.1.32、定理 10.1.36、定理 10.1.39 に対応する定理を必要な定義と共に示す:

定理 10.1.42、定理 10.1.44、定理 10.1.45 は有向グラフに対する同様の命題 (つまり定理 10.1.32、定理 10.1.36、定理 10.1.39) を \(G^{\operatorname*{bidir}}\) に適用すれば直ちに得られる (\(G\) の路と \(G^{\operatorname*{bidir}}\) の路の間に全単射が存在するため)。