Hall's theorem

OR事典

ホールの定理

読み方：ほーるのていり
【英】：Hall's theorem

2部グラフ において, 左側点集合 に関する完全マッチングが存在するための必要十分条件は次のように書ける:

この不等式の右辺は, 中に左側点をもつ枝の右側点の数を表す.この必要十分条件をホールの定理と呼ぶ. ケーニグ・ホールの定理 (K\"onig--Hall's Theorem) と呼ばれることもある.

「OR事典」の他の用語

グラフ･ネットワーク：

フェンシェル型双対定理  プリム法  ベルマン・フォード法  ホールの定理  ポリマトロイド  マッチング  マッチング問題

ウィキペディア

ホールの定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/14 20:57 UTC 版)

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

定義と表現

S = {S₁, S₂, ... } が有限集合の集まりとする（可算である必要はない）。Sの横断集合 (transversal) または S の完全代表系 (system of distinct representatives; SDR) とは、別個の元からなる集合 X = {x₁, x₂, ...}（ここで |X| = |S|）で、全ての i について x_i∈S_i となっている集合である。

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

$|T|\leq {\Bigl |}\bigcup _{A\in T}A{\Bigr |}$

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

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

議論と例

例 1: S = {S₁, S₂, S₃} があり、それぞれは以下の通り。

S₁ = {1, 2, 3}

S₂ = {1, 4, 5}

S₃ = {3, 5}

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

例 2: S = {S₁, S₂, S₃, S₄} があり、それぞれは以下の通り。

S₁ = {2, 3, 4, 5}

S₂ = {4, 5}

S₃ = {5}

S₄ = {4}

妥当なSDRは存在しない。また、部分集合 {S₂, S₃, S₄} について結婚条件が成り立たない。

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

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

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

この定理は結婚以外にもいろいろな場面に応用できる。例えば、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 の近傍を $N_{G}(W)$ で表す。近傍とは、W の何らかの元に隣接する全頂点の集合である。グラフ理論における結婚定理（ホールの定理）によれば、完全マッチングが存在することと X のあらゆる部分集合 W について次が成り立つことは同値である。

$|W|\leq |N_{G}(W)|$

言い換えれば、X のあらゆる部分集合 W は Y に属する頂点と十分に隣接している。

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

より一般化した表現

有限2部グラフ G:= (X + Y, E) で X と Y は同じ大きさでなくともよい。ここで、G の最大マッチングの端点がXをすべて覆うことと、X の全ての部分集合 W について次が成り立つことは同値である。

$|W|\leq |N_{G}(W)|$

グラフ理論による証明

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

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

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

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

論理的に等価な定理

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

• König's theorem
• Konig-Egervary theorem (1931) (Dénes Kőnig, Jenő Egerváry)
• メンガーの定理 (1927)
• 最大フロー最小カット定理
• バーコフ・フォン・ノイマンの定理 (1946)
• Dilworth's theorem

特に Dilworth's theorem ⇒ ホールの定理 ⇔ Konig-Egervary theorem ⇔ König's theorem という関係を導く単純な証明が存在する。

外部リンク

• Marriage Theorem at cut-the-knot
• Marriage Problem at cut-the-knot
• proof of Hall's marriage theorem PlanetMath