ホールの定理のソースを表示

{{otheruses}}
'''ホールの定理'''（{{lang-en-short|Hall's theorem}}）または'''結婚定理'''（{{lang-en-short|marriage theorem}}）は、[[組合せ数学]]の帰結の1つで、有限集合の集まりのそれぞれから別個の元を選択できる条件を与える。名称の由来は数学者の[[フィリップ・ホール]]（1904年-1982年）。

== 定義と表現 ==
''S'' = {''S''<sub>''1''</sub>, ''S''<sub>''2''</sub>, ... } が[[有限集合]]の集まりとする（[[可算集合|可算]]である必要はない）。''S''の[[横断集合]] (transversal) または ''S'' の'''完全代表系''' (''system of distinct representatives''; '''SDR''') とは、別個の元からなる集合 ''X'' = {''x''<sub>''1''</sub>, ''x''<sub>''2''</sub>, ...}（ここで |''X''| = |''S''|）で、全ての ''i'' について ''x''<sub>''i''</sub>&isin;''S''<sub>''i''</sub> となっている集合である。

''S''の'''結婚条件''' (marriage condition) とは、''S''の任意の部分集合 <math>T \subseteq S</math> についての次の条件である。

:<math>|T| \le \Bigl|\bigcup_{A \in T} A\Bigr|</math>

ここで、|''T''| は集合 ''T''の元の数を意味する。

ホールの定理は、SDR ''X'' が存在することと、''S'' が結婚条件を満たすことは[[同値]]であるというものである。

== 議論と例 ==
例 1: ''S'' = {''S''<sub>''1''</sub>, ''S''<sub>''2''</sub>, ''S''<sub>''3''</sub>} があり、それぞれは以下の通り。
:''S''<sub>''1''</sub> = {1, 2, 3}
:''S''<sub>''2''</sub> = {1, 4, 5}
:''S''<sub>''3''</sub> = {3, 5}

妥当なSDRは {1, 4, 5} である（ただし、これは唯一のSDRではない。例えば {2, 1, 3} でもよい）。

例 2: ''S'' = {''S''<sub>''1''</sub>, ''S''<sub>''2''</sub>, ''S''<sub>''3''</sub>, ''S''<sub>''4''</sub>} があり、それぞれは以下の通り。
:''S''<sub>''1''</sub> = {2, 3, 4, 5}
:''S''<sub>''2''</sub> = {4, 5}
:''S''<sub>''3''</sub> = {5}
:''S''<sub>''4''</sub> = {4}

妥当なSDRは存在しない。また、部分集合 {''S''<sub>''2''</sub>, ''S''<sub>''3''</sub>, ''S''<sub>''4''</sub>} について結婚条件が成り立たない。

結婚定理の一般的応用例は、''n''人の男性と''n''人の女性という2つのグループを想定する。それぞれの女性は男性の部分集合のいずれかと結婚できれば幸せである（結婚してもよいと思う男性が何人かいる）。また、それぞれの男性は自分と結婚したい（してもよい）と思っている女性と結婚できれば幸せである。ここで、全員が幸せになるような組合せ（[[結婚]]）は可能か、という問題である（男女を入れ替えた設定でもよい）。

ここで ''S''<sub>''i''</sub> を ''i''番目の女性が結婚して幸せになれる男性の集合とする。結婚定理によれば、それぞれの女性が男性と幸せな結婚をできることと、集合の集まり {''S''<sub>''1''</sub>, ''S''<sub>''2''</sub>, ...} が結婚条件を満たすことは同値である。

なお、この場合の結婚条件とは、女性の任意の部分集合 <math>I</math> について、結婚したら幸せだという女性が少なくとも1人以上いる男性の数 <math>|\bigcup _{i \in I} S_i|</math> がその部分集合に含まれる女性の人数 <math>|I|</math> 以上でなければならない。これが成り立たないと結婚対象となる男性の人数が（<math>I</math> に属する女性の人数に対して）足りないことを意味するので、この条件が必要条件であることは明らかである。興味深いことに、これは同時に十分条件でもある。

この定理は結婚以外にもいろいろな場面に応用できる。例えば、52枚の[[トランプ]]を4枚ずつ13の山に分けるとする。結婚定理をこれに適用すると、それぞれの山から1枚ずつカードを選んで、エースからキングまでの13枚を必ず揃えることができるといえる（スートは考慮しない）。

より抽象的な例としては、ある[[群 (数学)|群]] ''G'' があり、''H'' を ''G'' の有限な部分群とする。これに結婚定理を適用すると、''G'' における ''H'' の左剰余類の集合と右剰余類の集合のSDRであるような集合 ''X'' が必ず存在するといえる。

より一般的問題として、集合の集まりがあったときにそれぞれの集合から（別個とは限らない）元を選ぶことができるには、[[選択公理]]が成り立たなければならない。

== グラフ理論 ==
結婚定理は[[グラフ理論]]にも応用される。グラフ理論の用語で問題を表すと次のようになる。

有限な[[2部グラフ]] ''G'':= (''X'' + ''Y'', ''E'') で ''X'' と ''Y'' が同じ大きさとしたとき、[[マッチング (グラフ理論)|マッチング]]は存在するか? すなわち、''G'' の各頂点が必ず1つの辺と接合するような辺の集合は存在するか?

結婚定理がこの問題の答えを与える。

''G'' の頂点の集合 ''W'' について、''G'' における ''W'' の[[近傍 (グラフ理論)|近傍]]を <math>N_G(W)</math> で表す。近傍とは、''W'' の何らかの元に隣接する全頂点の集合である。グラフ理論における結婚定理（ホールの定理）によれば、完全マッチングが存在することと ''X'' のあらゆる部分集合 ''W'' について次が成り立つことは[[同値]]である。
:<math>|W| \leq |N_G(W)|</math>
言い換えれば、''X'' のあらゆる部分集合 ''W'' は ''Y'' に属する頂点と十分に隣接している。

任意のグラフに一般化したものが[[タットの定理]]である。

=== より一般化した表現 ===
有限2部グラフ ''G'':= (''X'' + ''Y'', ''E'') で ''X'' と ''Y'' は同じ大きさでなくともよい。ここで、''G'' の最大[[マッチング (グラフ理論)|マッチング]]の端点が''X''をすべて覆うことと、''X'' の全ての部分集合 ''W'' について次が成り立つことは[[同値]]である。
:<math>|W| \leq |N_G(W)|</math>

== グラフ理論による証明 ==

まず、2部グラフ ''G'' = (''X'' + ''Y'', ''E'' ) = ''G''(''X'', ''Y'' ) が ''X''-飽和マッチング（''X'' の全ての頂点を飽和するようなマッチング）を持つならば、任意の''W'' ⊆ ''X'' に対して|N<sub>''G''</sub>(''W'' )| ≥ |''W'' |であることを示す。

Mを''X''-飽和マッチングとする。
このとき、Mによって、与えられた''W'' ⊆ ''X'' とマッチングされている''Y'' の頂点集合をM(''W'' )と書くと、マッチングの定義より|M(''W'' )|=|''W'' |。
しかし、M(''W'' )の全ての元は''W'' の近傍に属するので、M(''W'' ) ⊆ N<sub>''G''</sub>(''W'' )である。
よって、 |N<sub>''G''</sub>(''W'' )| ≥  |M(''W'' )| であるから、|N<sub>''G''</sub>(''W'')| ≥ |''W'' |。

次に、任意の''W'' ⊆ X に対して|N<sub>''G''</sub>(''W'')| ≥ |''W'' | ならば、''G''(''X'',''Y'')は''X''-飽和マッチングを持つことを示す。

2部グラフ''G''(''X'',''Y'')が''X''-飽和マッチングを持たないと仮定して矛盾を導く。
''M'' を''G''の最大マッチングすると、''M''-非飽和点が存在するので、これを''u'' &isin; ''X'' とする。
''u'' を始点とする任意の''M''-交互道を考え、この交互道によって''u''と接続するすべての''Y'' の頂点の集合を''T'' とする。
同様に、''u''と接続するすべての''X'' の頂点の集合(''u'' 自身も含む)を''W'' とする。
''u'' を始点とする''M''-交互道の終点が、''Y''に属する点となること（つまり、''M''-増大道となること）はない。
（もしそのようなことがあれば、''M'' より真に大きなマッチングが構成でき、''M'' の最大性に矛盾する。）
ここで、''T'' に属する全ての頂点は、Mにより''W'' の頂点とマッチングされており、
逆に全ての頂点 ''v'' &isin; ''W'' \ {''u''} はMにより''T'' の頂点とマッチングされているので、
M は ''W'' \ {''u''} と ''T'' の間の全単射を与える。よって、 |''W'' | = |''T'' | + 1であり、N<sub>''G''</sub>(''W'') ⊇ ''T'' が成立する。
他方、''v'' &isin; ''Y'' を''w'' &isin; ''W'' に接続される頂点としたとき、辺 (''w'',''v'' ) が Mに属していれば、''v'' &isin; ''T''。
そうでなければ、辺 (''w'',''v'' ) を通る''M''-交互道を構成できるので、''v'' &isin; ''T''となり、N<sub>''G''</sub>(''W'') ⊆ ''T''が成立。
したがって、 |N<sub>''G''</sub>(''W'')| = |''T'' | = |''W'' | − 1 となり、矛盾。

== 論理的に等価な定理 ==
この定理は組合せ数学における非常に強力な一連の定理の1つである。それらの定理は形式的でない意味で互いに関連しており、いずれかの定理に基づいて別の定理を容易に導ける。これには以下のような定理が含まれる。

* [[:en:König's theorem (graph theory)|König's theorem]]
* Konig-Egervary theorem (1931) (Dénes Kőnig, Jenő Egerváry)
* [[メンガーの定理]] (1927)
* [[最大フロー最小カット定理]]
* [[二重確率行列|バーコフ・フォン・ノイマンの定理]] (1946)
* [[:en:Dilworth's theorem|Dilworth's theorem]]

特に Dilworth's theorem ⇒ ホールの定理 ⇔ Konig-Egervary theorem ⇔ König's theorem という関係を導く単純な証明が存在する<ref>[http://robertborgersen.info/Presentations/GS-05R-1.pdf Equivalence of seven major theorems in combinatorics]</ref>。

== 脚注・出典 ==
{{Reflist}}

== 外部リンク ==
* {{高校数学の美しい物語|904|Hallの結婚定理とその証明}}
* [http://www.cut-the-knot.org/arithmetic/elegant.shtml Marriage Theorem] at cut-the-knot
* [http://www.cut-the-knot.org/arithmetic/marriage.shtml Marriage Problem] at cut-the-knot
* [http://planetmath.org/?op=getobj&from=objects&id=3059 proof of Hall's marriage theorem] PlanetMath

{{DEFAULTSORT:ほるのていり}}
[[Category:グラフ理論の定理]]
[[Category:組合せ論の定理]]
[[Category:数学に関する記事]]