8.4. König の定理と Hall–König の定理

Hall の結婚定理には様々なバージョンが知られているものの、そのほとんどは前節の最後で示した命題と同値である (どちらかを仮定すれば、もう一方を容易に導ける)。本節で最初に紹介する König の定理 (1931 年に Dénes König と Jenő Egerváry が独立に発見した) は頂点被覆の概念を利用する。頂点被覆の定義を示す:

定義 8.4.1

\(G=\left( V,E,\varphi\right) \) を多重グラフとする。\(G\) の頂点被覆 (vertex cover) とは、\(V\) の部分集合 \(C\) であって条件「\(G\) の各辺が \(C\) に含まれる頂点を少なくとも一つ含む」を満たすものを言う。

例 8.4.2

\(n\geq1\) に対する完全グラフ \(K_{n}\) の頂点被覆はどんな集合だろうか？

少し考えれば、\(n-1\) 個以上の要素を持つ \(\left\{ 1,2,\ldots,n\right\} \) の任意の部分集合 \(S\) が \(K_{n}\) の頂点被覆であることが分かる (実際、\(K_{n}\) はループを持たないので \(K_{n}\) の各辺は異なる二頂点を接続する。よって、各辺に対応する二頂点の少なくとも一方は \(S\) に属する)。一方で、要素数が \(n-1\) より少ない \(\left\{ 1,2,\ldots,n\right\} \) の部分集合 \(S\) はどれも \(K_{n}\) の頂点被覆ではない (\(S\) に属さない \(K_{n}\) の頂点が少なくとも二つ存在し、その二つの頂点を接続する辺は \(S\) に属する頂点を含まないため)。

例 8.4.3

例 8.3.2 の一つ目のグラフを \(G=\left( V,E,\varphi\right) \) とする。このとき集合 \(\left\{ 2,5\right\} \) は \(G\) の頂点被覆である。もちろん、\(\left\{ 2,5\right\} \) を含む \(V\) の任意の部分集合もまた \(G\) の頂点被覆となる。

頂点被覆が (ある意味で) 辺被覆の「双対」であることに注意してほしい (辺被覆は練習問題 2.15 で定義した)。読者の理解を助けるため、Nadia Lafrenière, Math 38, Spring 2021 を参考にした分かりやすい表を次に示す:

\[ \begin{array}{|c|c|l|}\hline \textbf{... は} & \textbf{... の集合であり} & \hspace{55pt} \textbf{... という条件を満たす} \\ \hline\hline \text{マッチング} & \text{辺} & \text{任意の頂点 } v \text{ に対して } v \text{ を含む要素の個数が } 1 \text{ 以下} \\\hline \text{辺被覆} & \text{辺} & \text{任意の頂点 } v \text{ に対して } v \text{ を含む要素の個数が } 1 \text{ 以上} \\\hline \text{独立集合} & \text{頂点} & \text{任意の辺 } e \text{ に対して } e \text{ の端点である要素の個数が } 1 \text{ 以下} \\\hline \text{頂点被覆} & \text{頂点} & \text{任意の辺 } e \text{ に対して } e \text{ の端点である要素の個数が } 1 \text{ 以上} \\\hline \end{array} \]

頂点被覆は支配集合とも関係がある。つまり、次の命題が成り立つ:

Remark 8.4.4

次数が \(0\) の頂点を持たない多重グラフを \(G\) とする。\(G\) の頂点被覆は \(G\) の支配集合でもある。ただし、逆は成り立たない。

命題 8.4.5

\(G\) をループレスな多重グラフ、\(m\) を \(G\) のマッチングの最大要素数、\(c\) を \(G\) の頂点被覆の最小要素数とする。このとき \(m\leq c\) が成り立つ。

[証明] \(m\) の定義より、\(G\) は要素数 \(m\) のマッチング \(M\) を持つ。\(c\) の定義より、\(G\) は要素数 \(c\) の頂点被覆 \(C\) を持つ。

この \(M\) と \(C\) に注目する。\(C\) が頂点被覆なので、全ての \(M\)-辺 \(e \in M\) は \(C\) に含まれる頂点を少なくとも一つ含む。よって、各 \(M\)-辺 \(e\) を \(e\) に属する \(C\) の要素に対応付ける写像 \(f\colon M\rightarrow C\) を考えることができる (\(e\) に含まれる \(C\) の要素が複数あるときは任意に選ぶ)。\(M\) はマッチングより任意の二つの \(M\)-辺は同じ頂点を含まないので、この写像 \(f\) は単射である。\(M\) から \(C\) への単射の存在から \(\left\vert M\right\vert \leq\left\vert C\right\vert \) が分かる。一方 \(C\) と \(M\) の定義より \(\left\vert M\right\vert =m\) および \(\left\vert C\right\vert =c\) なので、\(m=\left\vert M\right\vert \leq\left\vert C\right\vert =c\) を得る。以上で命題 8.4.5 は証明された。□

一般のグラフでは命題 8.4.5 の \(m\) と \(c\) が \(m < c\) を満たすこともある。しかし、二部グラフでは等号が成り立つ:

定理 8.4.6

[König の定理 (König's theorem)] \(\left( G,X,Y\right) \) を二部グラフとする。\(m\) を \(G\) のマッチングの最大要素数、\(c\) を \(G\) の頂点被覆の最小要素数とする。このとき \(m=c\) が成り立つ。

Hall の結婚定理と König の定理はどちらも次の定理から容易に導ける:

定理 8.4.7

[Hall–König のマッチング定理 (Hall–König matching theorem)] \(\left( G,X,Y\right) \) を二部グラフとする。このとき、次の条件を満たす \(G\) のマッチング \(M\) と \(X\) の部分集合 \(U\) が存在する:

\[ \left\vert M\right\vert \geq\left\vert N\left( U\right) \right\vert +\left\vert X\right\vert -\left\vert U\right\vert \]

この定理は第 9.5 節と第 10.2.3 項で証明する。ここでは Hall の結婚定理 (定理 8.3.4) と König の定理 (定理 8.4.6) と Hall–König のマッチング定理 (定理 8.4.7) が同値なことを示す。正確に言えば、これから三つ目の定理を使って最初の二つの定理を証明し、さらに逆方向の導出を簡単に説明する。

[定理 8.4.7 を使った定理 8.3.4 の証明] 定理 8.4.7 が証明されたと仮定する。

定理 8.4.7 からは、次の条件を満たす \(G\) のマッチング \(M\) と \(X\) の部分集合 \(U\) が存在すると分かる:

\[ \left\vert M\right\vert \geq\left\vert N\left( U\right) \right\vert +\left\vert X\right\vert -\left\vert U\right\vert \]

この \(M\) と \(U\) に注目する。Hall 条件より、\(X\) の任意の部分集合 \(A\) は \(\left\vert N\left( A\right) \right\vert \geq\left\vert A\right\vert \) を満たす。この不等式で \(A=U\) とすれば \(\left\vert N\left( U\right) \right\vert \geq\left\vert U\right\vert \) を得る。よって次の不等式が分かる:

\[ \left\vert M\right\vert \geq\underbrace{\left\vert N\left( U\right) \right\vert }_{\geq\left\vert U\right\vert }+\left\vert X\right\vert -\left\vert U\right\vert \geq\left\vert X\right\vert \]

よって命題 8.3.1 (e) よりマッチング \(M\) は \(X\)-完全である。以上で定理 8.3.4 は (定理 8.4.7 を仮定して) 証明された。□

[定理 8.4.7 を使った定理 8.4.6 の証明] 定理 8.4.7 が証明されたと仮定する。

多重グラフ \(G\) を \(G=\left( V,E,\varphi\right) \) と書く。定理 8.4.7 より、次の不等式を満たす \(G\) のマッチング \(M\) と \(X\) の部分集合 \(U\) が存在する:

\[ \left\vert M\right\vert \geq\left\vert N\left( U\right) \right\vert +\left\vert X\right\vert -\left\vert U\right\vert \qquad (1) \]

この \(M\) と \(U\) に注目する。\(G\) のマッチングの最大要素数が \(m\) と定義されるので、\(\left\vert M\right\vert \leq m\) が分かる。

\(C\colonequals \left( X\setminus U\right) \cup N\left( U\right) \) と定める。\(C\) は \(V\) の部分集合である。さらに、容易に分かるように \(G\) の各辺は少なくとも一つの端点が \(C\) に属する¹。よって \(C\) は \(G\) の頂点被覆である。\(G\) の頂点被覆の最小要素数が \(c\) と定義されるので、次が分かる:

\[ \begin{aligned} c & \leq \left\vert C\right\vert \\ & =\left\vert \left( X\setminus U\right) \cup N\left( U\right) \right\vert \\ & \leq\underbrace{\left\vert X\setminus U\right\vert }_{\substack{=\left\vert X\right\vert -\left\vert U\right\vert \\[3pt](\because\ U\subseteq X)}}+\left\vert N\left( U\right) \right\vert \quad (\text{実際には等号}) \\ & =\left\vert X\right\vert -\left\vert U\right\vert +\left\vert N\left( U\right) \right\vert =\left\vert N\left( U\right) \right\vert +\left\vert X\right\vert -\left\vert U\right\vert \\ & \leq\left\vert M\right\vert \quad \left(\because\ \text{式 } (1)\right) \\ & \leq m \end{aligned} \]

よって \(c \leq m\) である。命題 8.4.5 より \(m\leq c\) だから、合わせれば \(m = c\) を得る。以上で定理 8.4.6 は証明された。□

逆に、Hall の結婚定理または König の定理から Hall–König のマッチング定理を示すのも難しくない:

[定理 8.3.4 を使った定理 8.4.7 の証明 (概略)] 定理 8.3.4 が証明されたと仮定する。

\(Y\) にダミー頂点を追加し、このダミー頂点と \(X\) の各頂点を接続する辺を追加する操作を考える。この操作を Hall 条件が成り立つまで、つまり \(\max\left\{ \left\vert A\right\vert -\left\vert N\left( A\right) \right\vert \mid A \subseteq X \right\} \) 回だけ行って得られるグラフを \(G^{\prime}\) とする。さらに、\(G^{\prime}\) を得るまでに \(Y\) に追加したダミー頂点全体の集合を \(D\) とする。

このとき \(Y^{\prime}=Y\cup D\) は \(G^{\prime}\) の右頂点全体の集合に等しい (\(G^{\prime}\) の左頂点全体の集合は \(X\) のままで変わらない)。二部グラフ \(\left( G^{\prime},X,Y^{\prime }\right) \) は Hall 条件を満たすので、定理 8.3.4 より \(G^{\prime}\) は \(X\)-完全なマッチングを持つ。このマッチングを \(M^{\prime}\) とする。\(M^{\prime}\) からダミー頂点を含む辺を除去すると、\(G\) のマッチング \(M\) が得られる。このマッチング \(M\) の要素数は次の不等式を満たす:

\[ \begin{aligned} \left\vert M\right\vert & = \left\vert M^{\prime}\right\vert -\underbrace{\left(\text{\# } M^{\prime} \text{ から除去された辺}\right) }_{\substack{\leq\,\left(\text{\# } \text{ダミー頂点}\right) \\[4pt](\because\ \text{各ダミー頂点を含む } M^{\prime}\text{-辺は最大でも一つ})}}\nonumber\\[30pt] & \geq\left\vert M^{\prime}\right\vert -\underbrace{\left(\text{\# } \text{ダミー頂点}\right) }_{\substack{=\,\max\,\left\{ \left\vert A\right\vert -\left\vert N\left( A\right) \right\vert \mid A \subseteq X\right\} \\[4pt](\because\ \text{ダミー頂点の定義})}}\nonumber\\[30pt] & =\left\vert M^{\prime}\right\vert -\max\left\{ \left\vert A\right\vert -\left\vert N\left( A\right) \right\vert \mid A \subseteq X\right\}\qquad (2) \end{aligned} \]

一方、有限集合の最大値はその集合の要素だから、次の等式を満たす \(X\) の部分集合 \(U\) が存在する:

\[ \max\left\{ \left\vert A\right\vert -\left\vert N\left( A\right) \right\vert \mid A \subseteq X\right\} =\left\vert U\right\vert -\left\vert N\left( U\right) \right\vert \]

この事実を使うと、式 \((2)\) を次のように変形できる:

\[ \begin{aligned} \left\vert M\right\vert & \geq \left\vert M^{\prime}\right\vert -\underbrace{\max\left\{ \left\vert A\right\vert -\left\vert N\left( A\right) \right\vert \mid A \subseteq X\right\} }_{=\left\vert U\right\vert -\left\vert N\left( U\right) \right\vert }\\ & \geq\underbrace{\left\vert M^{\prime}\right\vert }_{\substack{\geq\left\vert X\right\vert}}- (\left\vert U\right\vert -\left\vert N\left( U\right) \right\vert) \\ & \quad {\small (\because\ M^{\prime} \text{ は } X \text{-完全より、任意の } x \in X \text{ に対応する } M^{\prime} \text{-辺が存在する})} \\[3pt] & \geq\left\vert X\right\vert -\left( \left\vert U\right\vert -\left\vert N\left( U\right) \right\vert \right) \\[3pt] & =\left\vert N\left( U\right) \right\vert +\left\vert X\right\vert -\left\vert U\right\vert \end{aligned} \]

よって \(G\) のマッチング \(M\) と \(X\) の部分集合 \(U\) は \(\left\vert M\right\vert \geq\left\vert N\left( U\right) \right\vert +\left\vert X\right\vert -\left\vert U\right\vert \) を満たす。以上で定理 8.4.7 は (定理 8.3.4 を仮定して) 証明された。□

[定理 8.4.6 を使った定理 8.4.7 の証明] 定理 8.4.6 が証明されたと仮定する。

\(M\) を \(G\) の要素数最大のマッチング、\(C\) を \(G\) の要素数最小の頂点被覆とする。このとき定理 8.4.6 より \(\left\vert M\right\vert =\left\vert C\right\vert \) が分かる。

\(U\colonequals X\setminus C\) と定める。このとき \(N\left( U\right) \subseteq C\setminus X\) が成り立つ [なぜ？]。よって \(\left\vert N\left( U\right) \right\vert \leq\left\vert C\setminus X\right\vert \) であり、次を得る:

\[ \begin{aligned} \underbrace{\left\vert N\left( U\right) \right\vert }_{\leq\left\vert C\setminus X\right\vert }+\left\vert X\right\vert - \vert \underbrace{U}_{=X\setminus C} \vert &\leq\left\vert C\setminus X\right\vert +\underbrace{\left\vert X\right\vert -\left\vert X\setminus C\right\vert }_{=\left\vert C\cap X\right\vert } \\ & =\left\vert C\setminus X\right\vert+\left\vert C\cap X\right\vert \\ & =\left\vert C\right\vert \\ & =\left\vert M\right\vert \end{aligned} \]

つまり \(\left\vert M\right\vert \geq\left\vert N\left( U\right) \right\vert +\left\vert X\right\vert -\left\vert U\right\vert \) である。以上で定理 8.4.7 は (定理 8.4.6 を仮定して) 証明された。□

よって定理 8.4.7 は Hall の結婚定理と König の定理を含み、前者を証明できれば後者の二つも証明できたことになる。定理 8.4.7 は第 9.5 節と第 10.2.3 項で証明する。

証明: \(G\) の任意の辺を取って \(e\) とする。\(e\) の少なくとも一つの端点が \(C\) に属すると示せばよい。

\(\left( G,X,Y\right) \) が二部グラフだから、辺 \(e\) は \(X\) に属する端点を持つ。この端点を \(x\) とする。\(x\) は \(U\) に属するか属さないかのどちらかである。
- \(x\) が \(U\) に属するなら、\(e\) の \(x\) でない端点 \(y\) が \(N\left( U\right) \) に属する。よって \(N\left( U\right) \subseteq\left( X\setminus U\right) \cup N\left( U\right) =C\) より \(y\) は \(C\) にも属する。
- \(x\) が \(U\) に属さないなら、\(x\) は \(X\setminus U\) に属する。よって \(X\setminus U\subseteq\left( X\setminus U\right) \cup N\left( U\right) =C\) より \(x\) は \(C\) にも属する。
いずれの場合でも \(C\) に属する \(e\) の端点が少なくとも一つ存在する。よって示したい命題は証明された。 ↩︎