【グラフ理論】ホールの結婚定理とは? 定理の主張・名前の由来・証明について解説

2024.12/25

こんにちは!半沢です!

今回の記事ではグラフ理論におけるホールの結婚定理(Hall’s marriage thoerem)について解説したいと思います。

ホールの結婚定理は名前が面白いだけでなく,マッチングに関する定理として最も基本的なものです。

この記事ではホールの結婚定理の主張・名前の由来・2\,2\,通りの証明について詳しく解説したいと思います。

ホールの結婚定理の他分野への応用については別の記事で改めて書く予定ですので,お待ちください。

ぜひ読んでいってください。

ホールの結婚定理(Hall’s marriage theorem)

主張

ホールの結婚定理(グラフ理論ver.)

X,YX,Y\,を部集合とする2\,2\,部グラフG=G(X,Y)\,G=G(X,Y)\,(多重辺も許してもよい)において,
次の必要十分条件が成り立つ。

XX\,の全ての頂点を飽和するマッチングM\,M\,が存在する
X\Leftrightarrow X\,の任意の部分集合S\,S\not=\emptyset\,についてNG(S)S\,|N_G(S)|\geq |S|\,が成り立つ。

NG(S)S\,N_G(S)\cdots S\,内の点に隣接するG\,G\,の点の集合。

※今回はグラフ理論ver.で表しましたが,ホールの結婚定理は組み合わせ数学の表式で表されることもあります(元論文もその表式)。グラフ理論ver.を知っておけば特に問題はありませんが,気になる方は参考図書[2][2]を参照すると良いでしょう。もしくは要望が多い場合は加筆します。

名前の由来

名前の由来を理解するために,X,Y\,X,Y\,を部集合とする2\,2\,部グラフG(X,Y)\,G(X,Y)\,について,
マッチングの記事で解説した次のお見合いのイメージで考えましょう。

XX\,の点\,\cdots\,男性

YY\,の点\,\cdots\,女性

xy\,xy\,\,\cdots\,男性x\,x\,と女性y\,y\,がお互いに気になっている状態

マッチング\,\cdots\,お見合い結果

このようなお見合いにおいて,

「男性達X\,X\,全員に彼女ができて,結婚できるようなお見合い結果が存在するのはどのようなときか?」

という問題が考えられます。

数学的に言い換えれば
XX\,の全ての頂点を飽和するマッチングM\,M\,はどのようなときに存在するのか?」
ということですね。

主張を振り返れば,
ホールの結婚定理はこの結婚問題が解を持つための必要十分条件を表していることが分かります。

そのためこの定理を1935年に証明したPhilip Hallさんの名前を取って,ホールの結婚定理と呼ぶわけです。

次章ではホールの結婚定理の証明を見ていきましょう。

証明

それではホールの結婚定理の証明です。

主張\,\Rightarrow\,については,お見合いのイメージで考えれば明らかです。

なぜなら「男性達X\,X\,全員に彼女ができて,結婚できるようなお見合い結果が存在する」としましょう。

このときk\,k\,人の男性達S  (SX,S=k)\,S\,\,(S\subset X,|S|=k)\,の誰かとはお互いに気になっている状態にある女性達NG(S)\,N_G(S)\,を考えましょう。

するとk\,k\,人の男性達S\,S\,とお見合い後に結婚することとなるk\,k\,人の女性達はNG(S)\,N_G(S)\,に含まれるので,
NG(S)k=S|N_G(S)|\geq k = |S|\,となり\,\Rightarrow\,は示されました。

そのため,ここからは\,\Leftarrow\,2\,2\,通りの方法で示していきます。

数学的帰納法による証明

11\,つ目の証明についてはお見合いのイメージで考えやすいので,それに沿って考えていきましょう。

男性の人数X\,|X|\,に関する数学的帰納法で示していきます。
男性が1\,1\,人のときに\,\Leftarrow\,が成り立つのは明らかです。

そこで男性がk\,k\,人以下のときは\,\Leftarrow\,が成り立つと仮定して,
男性がk+1\,k+1\,人いるときについて考えていきましょう。

今前提としてどの男性達SX\,S\subset X\,についても,NG(S)S\,|N_G(S)|\geq |S|\,が成り立っています。

NG(S)S|N_G(S)|\geq |S|\,をもう少し柔らかく言えば
男性達S\,S\,の誰かとはお互いに気になっている状態にある女性達の人数は,その男性達よりも多い」ということですね。

そこで次の2\,2\,つの場合に分けて考えていきます。

(i)(\,\mathrm{i}\,)\,どのk\,k\,人以下の男性達S  (Sk)\,S\,\,(|S|\leq k)\,についても,NG(S)>S\,|N_G(S)|\gt |S|\,が成り立つ。

(ii)(\,\mathrm{ii}\,)\,あるk\,k\,人以下の男性達S0  (S0k)\,S_0\,\,(|S_0|\leq k)\,については,NG(S0)=S0\,|N_G(S_0)|= |S_0|\,となる。

まずは(i)\,(\,\mathrm{i}\,)\,の場合について考えていきましょう。

このとき適当な男性xX\,x\in X\,1\,1\,人選んで,その男性と気になり合っている状態にある女性y\,y\,をカップルにしてしまい,一旦2\,2\,人を退場させます。

※男性x\,x\,に対してそのような女性y\,y\,が存在することは,S={x}\,S=\{x\}\,の場合を考えるとNG(x)1\,N_G(x)\geq 1\,より保証されています。

22\,人を追い出した後のお見合いG=G{a,b}\,G’=G-\{a,b\}\,k\,k\,人の男性しかいません。

さらに女性が1\,1\,人消えただけなのでNG(S)>S\,|N_G(S)|\gt |S|\,から,
どの男性達SG\,S’\sub G’\,についてもNG(S)NG(S)1S\,|N_{G’}(S’)|\geq |N_{G}(S’)|-1 \geq |S’|\,となります。

よって帰納法の仮定が満たされたので,お見合いG\,G’\,では男性達全員は彼女を作ることができます。

お見合いG\,G’\,にいない男性x\,x\,も彼女y\,y\,がいるので,全体のお見合いG\,G\,では男性達全員は彼女を作ることができました。

つまり(i)\,(\,\mathrm{i}\,)\,については示すことが出来ました。

続いて(ii)\,(\,\mathrm{ii}\,)\,の場合について示していきましょう。

男性達S0\,S_0\,と女性達NG(S0)\,N_G(S_0)\,だけを集めてお見合いG0\,G_0\,を開きましょう。

男性達S0\,S_0\,k\,k\,人以下で,全体G\,G\,NG(S)S\,|N_G(S)|\geq |S|\,が成り立っていますので,お見合いG0\,G_0\,でも同様の条件が成り立っています。

よって帰納法の仮定を適用できて,お見合いG0\,G_0\,では全男性が彼女を作ることができます。

ここでお見合いG0\,G_0\,に参加していない残りの男性・女性たちで,お見合いGG0\,G-G_{0}\,を開きましょう。

このとき,このお見合いGG0\,G-G_{0}\,は帰納法の仮定を満たしています。

背理法によりこのことを示すため,仮にGG0\,G-G_{0}\,において,
あるl\,l\,人の男性達T\,T\,の誰かとお互いに気になっている状態にある女性NGG0(T)\,N_{G-G_0}(T)\,の人数がl\,l\,人未満だとしましょう。

これを全体のお見合いG\,G\,で考え直すとNG(S0)=S0\,|N_G(S_0)|= |S_0|\,より,
l+S0\,l+|S_0|\,人の男性達TS0\,T\cup S_0\,の誰かとお互いに気になっている女性はl+S0\,l+|S_0|\,人未満となります。

これはG\,G\,\,\Leftarrow\,の前提を満たすことに矛盾します。

またGG0\,G-G_{0}\,における男性の人数も明らかに大丈夫です。

よって帰納法の仮定からお見合いGG0\,G-G_{0}\,でも男性達全員は彼女を作ることができます。

G0\,G_0\,GG0\,G-G_{0}\,を合わせることで,全体GGにおいて男性達全員は彼女を作ることが出来ました。

つまり(ii)\,(\,\mathrm{ii}\,)\,についても示すことが出来ました。

したがって帰納法よりホールの結婚定理を証明することができました。\quad \square

M-M\text{-}交互道を利用した証明

22\,つ目の証明はM-\,M\text{-}交互道を利用した証明です。

\Leftarrow\,の前提条件である
X\,X\,の任意の部分集合S\,S\not=\emptyset\,についてNG(S)S\,|N_G(S)|\geq |S|\,」が成り立つとします。

背理法によって示すために,
G\,G\,のどんなマッチングもX\,X\,の全ての頂点を飽和することはないと仮定しましょう。

ここでG\,G\,の最大マッチングM\,M\,について考えましょう。

仮定よりM\,M\,に飽和されていない点xX\,x\in X\,を取ることができます。

このx\,x\,M-\,M\text{-}交互道で結ばれているG\,G\,の点の集合をW\,W\,とおきます。

ただしx\,x\,自身についてはxW\,x\in W\,とします。

さらにS=XW,T=YWS=X\cap W,T=Y\cap W\,とおきます。

このときW\,W\,の定義からN(S)=T\,N(S)=T\,が従うことを確認しましょう。

まずN(S)T\,N(S)\supset T\,についてです。

tT=YW\,t\in T=Y\cap W\,W\,W\,の定義から次のような状況になっています。

※マッチングM\,M\,に属する辺はで塗っています。

この交互道xxt\,x\cdots x’t\,からt\,t\,を除いたxx\,x\cdots x’\,ももちろん交互道ですので,xS\,x’\in S\,です。

そのためtN(S)\,t\in N(S)\,となり,N(S)T\,N(S)\supset T\,は分かります。

逆のN(S)T\,N(S)\subset T\,についてもほぼ同様です。

vN(S)\,v\in N(S)に対して,その隣接点sS\,s\in S\,が存在します。

sSs\in S\,より交互道xs\,x\cdots s\,により次のような状況になっています。

x\,x\,は飽和されていないので,交互道xs\,x\cdots s\,の最初の辺は必ずで塗られていることに注意しましょう(後の議論でも暗黙的に使用するので押さえておきましょう)。

すると交互道xs\,x\cdots s\,の最後の辺は必ずで塗られていることが分かりますね。

つまり点s\,s\,は既に飽和されているため辺sv\,sv\,で塗られています(図で?\,?\,の部分がで確定するということです)。

よって交互道xsv\,x\cdots sv\,が取れるので,vT\,v\in TN(S)T\,N(S)\subset T\,となります。

以上よりN(S)T\,N(S)\supset T\,は示されました。

次にM\,M\,の最大性からT=S1\,|T|=|S|-1\,となることを確認しましょう。

そのためにはS{x}\,S-\{x\}\,の点とT\,T\,の点が1\,1\,1\,1\,対応(全単射の意)することを言えばよいですね。

S{x}S-\{x\}\,の点s\,s\,は定義から交互道xts\,x\cdots ts\,が取れます。

下の図より明らかにstM\,{\color{#f2541d}st}\in M\,となる点tT\,t\in T\,が取れますね。

つまりS{x}\,S-\{x\}\,の点に対し,その点とマッチングで結ばれているT\,T\,の点を対応させることができます。

逆にT\,T\,の点t\,t\,についても定義から交互道xt\,x\cdots t\,が取れます。

もし点t\,t\,が飽和されていないとすると,xt\,x\cdots t\,は増大道になりM\,M\,の最大性に矛盾します。

よってstM\,{\color{#f2541d}st}\in M\,となる点sX\,s\in X\,の存在が分かります。

明らかにxts\,x\cdots ts\,は交互道なので,
結果的にこれはstM\,{\color{#f2541d}st}\in M\,となる点sS\,s\in S\,の存在が分かりました。

つまり逆にT\,T\,の点に対し,その点とマッチングで結ばれているS{x}\,S-\{x\}\,の点を対応させることもできました。

故にT=S{x}=S1\,|T|=|S-\{x\}|=|S|-1\,が成り立つことも分かりました。

後はここまでで証明したN(S)=T,T=S1\,N(S)=T,|T|=|S|-1\,を用いれば

NG(S)=T=S1<S|N_G(S)|=|T|=|S|-1\lt |S|\,

となり,\,\Leftarrow\,の前提条件に矛盾することが分かります。

したがって背理法よりホールの結婚定理は示されました。\quad\square

まとめ

今回の記事ではホールの結婚定理(Hall’s marriage thoerem)を解説いたしました。

定理の主張や名前の由来を理解することはできましたか?

ここで紹介した2\,2\,通りの証明以外の証明についても,要望があれば私が調査して加筆したいと思います。

※例えばメンガーの定理やシュペルナーの補題を認めることで証明ができるらしいです。

また定理の応用については別の記事で改めて書く予定ですので,お待ちいただけると嬉しいです。

もし「説明がわかりにくい」などご要望・ご感想がありましたら,
X(旧:Twitter)で#トイカラでつぶやいていただけると,できる限り対応します。

ここまで読んでいただき,ありがとうございました。

参考図書

  • [1][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][2] Martin Aigner,Günter M. Ziegler.”Proofs from THE BOOK”.Sixth Edition.Springer.2018出版.p.215-217.

人気記事ランキング

  • 【超基本_小学校レベル第9回】速さ 算数における時間の表し方・単位換算,時速・分速・秒速の変換,距離・速さ・時間の関係,平均の速さ

  • 【グラフ理論】隣接行列とは? 定義・イメージから隣接行列の固有値の重要性についても解説

  • 【超基本_小学校レベル第6回】四則演算の計算する順番 計算の工夫

  • 【受験生必見!】京大数学の整数問題に有効な「フェルマーの小定理」を紹介

  • 【東大受験生必見!】東大数学の体積問題の解き方 ~おまけ~

新着記事

  • 【解析学】リーマンゼータ関数の整数における特殊値は? 証明も含めて解説

    2025.04/03

  • 【複素解析学】cot\,\cot\,の部分分数分解! 留数定理による証明を解説

    2025.04/01

  • 【解析学】cot\,\cot\,の部分分数分解! 美しいヘルグロッツの技法による証明を解説

    2025.03/31

  • オリジナル問題集

    2025.03/21

  • 【グラフ理論】ライツアウトとは? 遊び方から全ライトがONの状態は消灯できることの証明まで解説

    2025.03/20