【グラフ理論】ホールの結婚定理とは？ 定理の主張・名前の由来・証明について解説
こんにちは！半沢です！
今回の記事ではグラフ理論におけるホールの結婚定理(Hall’s marriage thoerem)について解説したいと思います。
ホールの結婚定理は名前が面白いだけでなく，マッチングに関する定理として最も基本的なものです。
この記事ではホールの結婚定理の主張・名前の由来・\(\,2\,\)通りの証明について詳しく解説したいと思います。
ホールの結婚定理の他分野への応用については別の記事で改めて書く予定ですので，お待ちください。
ぜひ読んでいってください。
ホールの結婚定理(Hall’s marriage theorem)
主張
ホールの結婚定理(グラフ理論ver.)
\(X,Y\,\)を部集合とする\(\,2\,\)部グラフ\(\,G=G(X,Y)\,\)(多重辺も許してもよい)において，
次の必要十分条件が成り立つ。
\(X\,\)の全ての頂点を飽和するマッチング\(\,M\,\)が存在する
\(\Leftrightarrow X\,\)の任意の部分集合\(\,S\not=\emptyset\,\)について\(\,|N_G(S)|\geq |S|\,\)が成り立つ。
※\(\,N_G(S)\cdots S\,\)内の点に隣接する\(\,G\,\)の点の集合。
※今回はグラフ理論ver.で表しましたが，ホールの結婚定理は組み合わせ数学の表式で表されることもあります(元論文もその表式)。グラフ理論ver.を知っておけば特に問題はありませんが，気になる方は参考図書\([2]\)を参照すると良いでしょう。もしくは要望が多い場合は加筆します。
名前の由来
名前の由来を理解するために，\(\,X,Y\,\)を部集合とする\(\,2\,\)部グラフ\(\,G(X,Y)\,\)について，
マッチングの記事で解説した次のお見合いのイメージで考えましょう。
\(X\,\)の点\(\,\cdots\,\)男性
\(Y\,\)の点\(\,\cdots\,\)女性
辺\(\,xy\,\)\(\,\cdots\,\)男性\(\,x\,\)と女性\(\,y\,\)がお互いに気になっている状態
マッチング\(\,\cdots\,\)お見合い結果
このようなお見合いにおいて，
「男性達\(\,X\,\)全員に彼女ができて，結婚できるようなお見合い結果が存在するのはどのようなときか？」
という問題が考えられます。
数学的に言い換えれば
「\(X\,\)の全ての頂点を飽和するマッチング\(\,M\,\)はどのようなときに存在するのか？」
ということですね。
主張を振り返れば，
ホールの結婚定理はこの結婚問題が解を持つための必要十分条件を表していることが分かります。
そのためこの定理を1935年に証明したPhilip Hallさんの名前を取って，ホールの結婚定理と呼ぶわけです。
次章ではホールの結婚定理の証明を見ていきましょう。
証明
それではホールの結婚定理の証明です。
主張の\(\,\Rightarrow\,\)については，お見合いのイメージで考えれば明らかです。
なぜなら「男性達\(\,X\,\)全員に彼女ができて，結婚できるようなお見合い結果が存在する」としましょう。
このとき\(\,k\,\)人の男性達\(\,S\,\,(S\subset X,|S|=k)\,\)の誰かとはお互いに気になっている状態にある女性達\(\,N_G(S)\,\)を考えましょう。
すると\(\,k\,\)人の男性達\(\,S\,\)とお見合い後に結婚することとなる\(\,k\,\)人の女性達は\(\,N_G(S)\,\)に含まれるので，
\(|N_G(S)|\geq k = |S|\,\)となり\(\,\Rightarrow\,\)は示されました。
そのため，ここからは\(\,\Leftarrow\,\)を\(\,2\,\)通りの方法で示していきます。
数学的帰納法による証明
\(1\,\)つ目の証明についてはお見合いのイメージで考えやすいので，それに沿って考えていきましょう。
男性の人数\(\,|X|\,\)に関する数学的帰納法で示していきます。
男性が\(\,1\,\)人のときに\(\,\Leftarrow\,\)が成り立つのは明らかです。
そこで男性が\(\,k\,\)人以下のときは\(\,\Leftarrow\,\)が成り立つと仮定して，
男性が\(\,k+1\,\)人いるときについて考えていきましょう。
今前提としてどの男性達\(\,S\subset X\,\)についても，\(\,|N_G(S)|\geq |S|\,\)が成り立っています。
\(|N_G(S)|\geq |S|\,\)をもう少し柔らかく言えば
「男性達\(\,S\,\)の誰かとはお互いに気になっている状態にある女性達の人数は，その男性達よりも多い」ということですね。
そこで次の\(\,2\,\)つの場合に分けて考えていきます。
\((\,\mathrm{i}\,)\,\)どの\(\,k\,\)人以下の男性達\(\,S\,\,(|S|\leq k)\,\)についても，\(\,|N_G(S)|\gt |S|\,\)が成り立つ。
\((\,\mathrm{ii}\,)\,\)ある\(\,k\,\)人以下の男性達\(\,S_0\,\,(|S_0|\leq k)\,\)については，\(\,|N_G(S_0)|= |S_0|\,\)となる。
まずは\(\,(\,\mathrm{i}\,)\,\)の場合について考えていきましょう。
このとき適当な男性\(\,x\in X\,\)を\(\,1\,\)人選んで，その男性と気になり合っている状態にある女性\(\,y\,\)をカップルにしてしまい，一旦\(\,2\,\)人を退場させます。
※男性\(\,x\,\)に対してそのような女性\(\,y\,\)が存在することは，\(\,S=\{x\}\,\)の場合を考えると\(\,N_G(x)\geq 1\,\)より保証されています。
\(2\,\)人を追い出した後のお見合い\(\,G’=G-\{a,b\}\,\)は\(\,k\,\)人の男性しかいません。
さらに女性が\(\,1\,\)人消えただけなので\(\,|N_G(S)|\gt |S|\,\)から，
どの男性達\(\,S’\sub G’\,\)についても\(\,|N_{G’}(S’)|\geq |N_{G}(S’)|-1 \geq |S’|\,\)となります。
よって帰納法の仮定が満たされたので，お見合い\(\,G’\,\)では男性達全員は彼女を作ることができます。
お見合い\(\,G’\,\)にいない男性\(\,x\,\)も彼女\(\,y\,\)がいるので，全体のお見合い\(\,G\,\)では男性達全員は彼女を作ることができました。
つまり\(\,(\,\mathrm{i}\,)\,\)については示すことが出来ました。
続いて\(\,(\,\mathrm{ii}\,)\,\)の場合について示していきましょう。
男性達\(\,S_0\,\)と女性達\(\,N_G(S_0)\,\)だけを集めてお見合い\(\,G_0\,\)を開きましょう。
男性達\(\,S_0\,\)は\(\,k\,\)人以下で，全体\(\,G\,\)で\(\,|N_G(S)|\geq |S|\,\)が成り立っていますので，お見合い\(\,G_0\,\)でも同様の条件が成り立っています。
よって帰納法の仮定を適用できて，お見合い\(\,G_0\,\)では全男性が彼女を作ることができます。
ここでお見合い\(\,G_0\,\)に参加していない残りの男性・女性たちで，お見合い\(\,G-G_{0}\,\)を開きましょう。
このとき，このお見合い\(\,G-G_{0}\,\)は帰納法の仮定を満たしています。
背理法によりこのことを示すため，仮に\(\,G-G_{0}\,\)において，
ある\(\,l\,\)人の男性達\(\,T\,\)の誰かとお互いに気になっている状態にある女性\(\,N_{G-G_0}(T)\,\)の人数が\(\,l\,\)人未満だとしましょう。
これを全体のお見合い\(\,G\,\)で考え直すと\(\,|N_G(S_0)|= |S_0|\,\)より，
\(\,l+|S_0|\,\)人の男性達\(\,T\cup S_0\,\)の誰かとお互いに気になっている女性は\(\,l+|S_0|\,\)人未満となります。
これは\(\,G\,\)が\(\,\Leftarrow\,\)の前提を満たすことに矛盾します。
また\(\,G-G_{0}\,\)における男性の人数も明らかに大丈夫です。
よって帰納法の仮定からお見合い\(\,G-G_{0}\,\)でも男性達全員は彼女を作ることができます。
\(\,G_0\,\)と\(\,G-G_{0}\,\)を合わせることで，全体\(G\)において男性達全員は彼女を作ることが出来ました。
つまり\(\,(\,\mathrm{ii}\,)\,\)についても示すことが出来ました。
したがって帰納法よりホールの結婚定理を証明することができました。\(\quad \square\)
\(M\text{-}\)交互道を利用した証明
\(2\,\)つ目の証明は\(\,M\text{-}\)交互道を利用した証明です。
\(\Leftarrow\,\)の前提条件である
「 \(\,X\,\)の任意の部分集合\(\,S\not=\emptyset\,\)について\(\,|N_G(S)|\geq |S|\,\)」が成り立つとします。
背理法によって示すために，
\(\,G\,\)のどんなマッチングも\(\,X\,\)の全ての頂点を飽和することはないと仮定しましょう。
ここで\(\,G\,\)の最大マッチング\(\,M\,\)について考えましょう。
仮定より\(\,M\,\)に飽和されていない点\(\,x\in X\,\)を取ることができます。
この\(\,x\,\)と\(\,M\text{-}\)交互道で結ばれている\(\,G\,\)の点の集合を\(\,W\,\)とおきます。
ただし\(\,x\,\)自身については\(\,x\in W\,\)とします。
さらに\(S=X\cap W,T=Y\cap W\,\)とおきます。
このとき\(\,W\,\)の定義から\(\,N(S)=T\,\)が従うことを確認しましょう。
まず\(\,N(S)\supset T\,\)についてです。
点\(\,t\in T=Y\cap W\,\)は\(\,W\,\)の定義から次のような状況になっています。
※マッチング\(\,M\,\)に属する辺は赤で塗っています。
この交互道\(\,x\cdots x’t\,\)から\(\,t\,\)を除いた\(\,x\cdots x’\,\)ももちろん交互道ですので，\(\,x’\in S\,\)です。
そのため\(\,t\in N(S)\,\)となり，\(\,N(S)\supset T\,\)は分かります。
逆の\(\,N(S)\subset T\,\)についてもほぼ同様です。
点\(\,v\in N(S)\)に対して，その隣接点\(\,s\in S\,\)が存在します。
\(s\in S\,\)より交互道\(\,x\cdots s\,\)により次のような状況になっています。
点\(\,x\,\)は飽和されていないので，交互道\(\,x\cdots s\,\)の最初の辺は必ず黒で塗られていることに注意しましょう(後の議論でも暗黙的に使用するので押さえておきましょう)。
すると交互道\(\,x\cdots s\,\)の最後の辺は必ず赤で塗られていることが分かりますね。
つまり点\(\,s\,\)は既に飽和されているため辺\(\,sv\,\)は黒で塗られています(図で\(\,?\,\)の部分が黒で確定するということです)。
よって交互道\(\,x\cdots sv\,\)が取れるので，\(\,v\in T\)で\(\,N(S)\subset T\,\)となります。
以上より\(\,N(S)\supset T\,\)は示されました。
次に\(\,M\,\)の最大性から\(\,|T|=|S|-1\,\)となることを確認しましょう。
そのためには\(\,S-\{x\}\,\)の点と\(\,T\,\)の点が\(\,1\,\)対\(\,1\,\)対応(全単射の意)することを言えばよいですね。
\(S-\{x\}\,\)の点\(\,s\,\)は定義から交互道\(\,x\cdots ts\,\)が取れます。
下の図より明らかに\(\,{\color{#f2541d}st}\in M\,\)となる点\(\,t\in T\,\)が取れますね。
つまり\(\,S-\{x\}\,\)の点に対し，その点とマッチングで結ばれている\(\,T\,\)の点を対応させることができます。
逆に\(\,T\,\)の点\(\,t\,\)についても定義から交互道\(\,x\cdots t\,\)が取れます。
もし点\(\,t\,\)が飽和されていないとすると，\(\,x\cdots t\,\)は増大道になり\(\,M\,\)の最大性に矛盾します。
よって\(\,{\color{#f2541d}st}\in M\,\)となる点\(\,s\in X\,\)の存在が分かります。
明らかに\(\,x\cdots ts\,\)は交互道なので，
結果的にこれは\(\,{\color{#f2541d}st}\in M\,\)となる点\(\,s\in S\,\)の存在が分かりました。
つまり逆に\(\,T\,\)の点に対し，その点とマッチングで結ばれている\(\,S-\{x\}\,\)の点を対応させることもできました。
故に\(\,|T|=|S-\{x\}|=|S|-1\,\)が成り立つことも分かりました。
後はここまでで証明した\(\,N(S)=T,|T|=|S|-1\,\)を用いれば
\(|N_G(S)|=|T|=|S|-1\lt |S|\,\)
となり，\(\,\Leftarrow\,\)の前提条件に矛盾することが分かります。
したがって背理法よりホールの結婚定理は示されました。\(\quad\square\)
まとめ
今回の記事ではホールの結婚定理(Hall’s marriage thoerem)を解説いたしました。
定理の主張や名前の由来を理解することはできましたか？
ここで紹介した\(\,2\,\)通りの証明以外の証明についても，要望があれば私が調査して加筆したいと思います。
※例えばメンガーの定理やシュペルナーの補題を認めることで証明ができるらしいです。
また定理の応用については別の記事で改めて書く予定ですので，お待ちいただけると嬉しいです。
もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。
ここまで読んでいただき，ありがとうございました。
参考図書
- \([1]\) Hall, P. (1935), On Representatives of Subsets. Journal of the London Mathematical Society, s1-10: 26-30. https://doi.org/10.1112/jlms/s1-10.37.26
- \([2]\) Martin Aigner,Günter M. Ziegler.”Proofs from THE BOOK”.Sixth Edition.Springer.2018出版.p.215-217.
