【グラフ理論】ホールの結婚定理とは? 定理の主張・名前の由来・証明について解説
こんにちは!半沢です!
今回の記事ではグラフ理論におけるホールの結婚定理(Hall’s marriage thoerem)について解説したいと思います。
ホールの結婚定理は名前が面白いだけでなく,マッチングに関する定理として最も基本的なものです。
この記事ではホールの結婚定理の主張・名前の由来・通りの証明について詳しく解説したいと思います。
ホールの結婚定理の他分野への応用については別の記事で改めて書く予定ですので,お待ちください。
ぜひ読んでいってください。
ホールの結婚定理(Hall’s marriage theorem)
主張
ホールの結婚定理(グラフ理論ver.)
を部集合とする部グラフ(多重辺も許してもよい)において,
次の必要十分条件が成り立つ。
の全ての頂点を飽和するマッチングが存在する
の任意の部分集合についてが成り立つ。
※内の点に隣接するの点の集合。
※今回はグラフ理論ver.で表しましたが,ホールの結婚定理は組み合わせ数学の表式で表されることもあります(元論文もその表式)。グラフ理論ver.を知っておけば特に問題はありませんが,気になる方は参考図書を参照すると良いでしょう。もしくは要望が多い場合は加筆します。
名前の由来
名前の由来を理解するために,を部集合とする部グラフについて,
マッチングの記事で解説した次のお見合いのイメージで考えましょう。
の点男性
の点女性
辺男性と女性がお互いに気になっている状態
マッチングお見合い結果
このようなお見合いにおいて,
「男性達全員に彼女ができて,結婚できるようなお見合い結果が存在するのはどのようなときか?」
という問題が考えられます。
数学的に言い換えれば
「の全ての頂点を飽和するマッチングはどのようなときに存在するのか?」
ということですね。
主張を振り返れば,
ホールの結婚定理はこの結婚問題が解を持つための必要十分条件を表していることが分かります。
そのためこの定理を1935年に証明したPhilip Hallさんの名前を取って,ホールの結婚定理と呼ぶわけです。
次章ではホールの結婚定理の証明を見ていきましょう。
証明
それではホールの結婚定理の証明です。
主張のについては,お見合いのイメージで考えれば明らかです。
なぜなら「男性達全員に彼女ができて,結婚できるようなお見合い結果が存在する」としましょう。
このとき人の男性達の誰かとはお互いに気になっている状態にある女性達を考えましょう。
すると人の男性達とお見合い後に結婚することとなる人の女性達はに含まれるので,
となりは示されました。
そのため,ここからはを通りの方法で示していきます。
数学的帰納法による証明
つ目の証明についてはお見合いのイメージで考えやすいので,それに沿って考えていきましょう。
男性の人数に関する数学的帰納法で示していきます。
男性が人のときにが成り立つのは明らかです。
そこで男性が人以下のときはが成り立つと仮定して,
男性が人いるときについて考えていきましょう。
今前提としてどの男性達についても,が成り立っています。
をもう少し柔らかく言えば
「男性達の誰かとはお互いに気になっている状態にある女性達の人数は,その男性達よりも多い」ということですね。
そこで次のつの場合に分けて考えていきます。
どの人以下の男性達についても,が成り立つ。
ある人以下の男性達については,となる。
まずはの場合について考えていきましょう。
このとき適当な男性を人選んで,その男性と気になり合っている状態にある女性をカップルにしてしまい,一旦人を退場させます。
※男性に対してそのような女性が存在することは,の場合を考えるとより保証されています。
人を追い出した後のお見合いは人の男性しかいません。
さらに女性が人消えただけなのでから,
どの男性達についてもとなります。
よって帰納法の仮定が満たされたので,お見合いでは男性達全員は彼女を作ることができます。
お見合いにいない男性も彼女がいるので,全体のお見合いでは男性達全員は彼女を作ることができました。
つまりについては示すことが出来ました。
続いての場合について示していきましょう。
男性達と女性達だけを集めてお見合いを開きましょう。
男性達は人以下で,全体でが成り立っていますので,お見合いでも同様の条件が成り立っています。
よって帰納法の仮定を適用できて,お見合いでは全男性が彼女を作ることができます。
ここでお見合いに参加していない残りの男性・女性たちで,お見合いを開きましょう。
このとき,このお見合いは帰納法の仮定を満たしています。
背理法によりこのことを示すため,仮ににおいて,
ある人の男性達の誰かとお互いに気になっている状態にある女性の人数が人未満だとしましょう。
これを全体のお見合いで考え直すとより,
人の男性達の誰かとお互いに気になっている女性は人未満となります。
これはがの前提を満たすことに矛盾します。
またにおける男性の人数も明らかに大丈夫です。
よって帰納法の仮定からお見合いでも男性達全員は彼女を作ることができます。
とを合わせることで,全体において男性達全員は彼女を作ることが出来ました。
つまりについても示すことが出来ました。
したがって帰納法よりホールの結婚定理を証明することができました。
交互道を利用した証明
つ目の証明は交互道を利用した証明です。
の前提条件である
「 の任意の部分集合について」が成り立つとします。
背理法によって示すために,
のどんなマッチングもの全ての頂点を飽和することはないと仮定しましょう。
ここでの最大マッチングについて考えましょう。
仮定よりに飽和されていない点を取ることができます。
このと交互道で結ばれているの点の集合をとおきます。
ただし自身についてはとします。
さらにとおきます。
このときの定義からが従うことを確認しましょう。
まずについてです。
点はの定義から次のような状況になっています。
※マッチングに属する辺は赤で塗っています。
この交互道からを除いたももちろん交互道ですので,です。
そのためとなり,は分かります。
逆のについてもほぼ同様です。
点に対して,その隣接点が存在します。
より交互道により次のような状況になっています。
点は飽和されていないので,交互道の最初の辺は必ず黒で塗られていることに注意しましょう(後の議論でも暗黙的に使用するので押さえておきましょう)。
すると交互道の最後の辺は必ず赤で塗られていることが分かりますね。
つまり点は既に飽和されているため辺は黒で塗られています(図での部分が黒で確定するということです)。
よって交互道が取れるので,でとなります。
以上よりは示されました。
次にの最大性からとなることを確認しましょう。
そのためにはの点との点が対対応(全単射の意)することを言えばよいですね。
の点は定義から交互道が取れます。
下の図より明らかにとなる点が取れますね。
つまりの点に対し,その点とマッチングで結ばれているの点を対応させることができます。
逆にの点についても定義から交互道が取れます。
もし点が飽和されていないとすると,は増大道になりの最大性に矛盾します。
よってとなる点の存在が分かります。
明らかには交互道なので,
結果的にこれはとなる点の存在が分かりました。
つまり逆にの点に対し,その点とマッチングで結ばれているの点を対応させることもできました。
故にが成り立つことも分かりました。
後はここまでで証明したを用いれば
となり,の前提条件に矛盾することが分かります。
したがって背理法よりホールの結婚定理は示されました。
まとめ
今回の記事ではホールの結婚定理(Hall’s marriage thoerem)を解説いたしました。
定理の主張や名前の由来を理解することはできましたか?
ここで紹介した通りの証明以外の証明についても,要望があれば私が調査して加筆したいと思います。
※例えばメンガーの定理やシュペルナーの補題を認めることで証明ができるらしいです。
また定理の応用については別の記事で改めて書く予定ですので,お待ちいただけると嬉しいです。
もし「説明がわかりにくい」などご要望・ご感想がありましたら,
X(旧:Twitter)で#トイカラでつぶやいていただけると,できる限り対応します。
ここまで読んでいただき,ありがとうございました。
参考図書
- 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
- Martin Aigner,Günter M. Ziegler.”Proofs from THE BOOK”.Sixth Edition.Springer.2018出版.p.215-217.