有限幾何学第13回 Hallの結婚定理次の結婚問題を考える．男性の有限集合があり，各男性は何人かの女性と知り合いであるとする．すべての男性が知り合いの女性と結婚できるように，カップルが組めるにはどんな条件が必要か？男性男性と知り合いの女性東方御坂，白井，初春虹村御坂岸部佐天，食蜂，白井空条佐天，白井 Hallの結婚定理男性の集合をV1, 女性の集合をV2とすると，この問題は次の用語を用いることで 2部グラフG(V1,V2)の問題に置き換えて考えることができる． M⊆E(G)がV1からV2への完全マッチングであるとは • Mに属する辺は端点を共有しないかつ • V1に属する任意の頂点はMに属するある辺の端点である Hallの結婚定理 M⊆E(G)がV1からV2への完全マッチングであるとは • Mに属する辺は端点を共有しないかつ • V1に属する任意の頂点はMに属するある辺の端点である V1 V2 Hallの結婚定理 Hallの結婚定理 G=G(V1,V2)：部集合がV1とV2の2部グラフ V1からV2への完全マッチングが存在する ⇔ V1の任意の部分集合Aに対して，|NG(A)|≧|A| NG(A)=∪v∊ANG(v) Hallの結婚定理 Hallの結婚定理の証明： V1からV2への完全マッチングが存在する ⇒ V1の任意の部分集合Aに対して，|NG(A)|≧|A| の証明： V1からV2への完全マッチングMによって誘導される誘導部分グラフをG’とすると， V1の任意の部分集合Aに対して，|A|=|NG’(A)|≦|NG(A)| Hallの結婚定理 Hallの結婚定理の証明：（⇐の証明） V1={ v1,v2,…, vn}とおく． nに関する帰納法で証明する．（ n=1のときは明らか） V1の真部分集合Aに対して， |NG(A)|=|A|であるとき，Aを臨界集合と呼ぶ．臨界集合が存在するか，存在しないかに分けて証明する． Hallの結婚定理 Hallの結婚定理の証明：（⇐の証明）場合1：臨界集合が存在しない場合 x∊NG(vn)を選ぶ（どれでもよい）． G’をGからvnとxを取り除いた結果生じるグラフとする．このとき，臨界集合が存在しないことから， V1-{vn}の任意の部分集合Aに対して， |NG’(A)|≧ |NG(A)|-|{x}|≧|A|+1-|{x}|=|A| よってG’に対して帰納法の仮定を適用することで V1-{vn}からV2への完全マッチングMが存在することが分かる．このとき，M∪{xvn}がV1からV2への完全マッチングとなる． Hallの結婚定理 Hallの結婚定理の証明：（⇐の証明）場合2：臨界集合が存在する場合 V1’={v1, v2,…, vl}を臨界集合としてよい（注：l < n）． V2’=NG(V1’)とおき， G’をV1’ ∪V2’によって誘導される誘導部分グラフとする．注：V1’は臨界集合なので|V2’|=|NG(V1’)|=|V1’| このとき， V1’の任意の部分集合Aに対して，|NG’(A)|=|NG(A)|≧|A| よってG’に対して帰納法の仮定を適用することで V1’からV2’への完全マッチングM1が存在することが分かる． Hallの結婚定理 Hallの結婚定理の証明：（⇐の証明）場合2：臨界集合が存在する場合 V1’’= V1-V1’ , V2’’= V2-V2’ とする． G’’をV1’’ ∪V2’’によって誘導される誘導部分グラフとする．このとき， V1’’の任意の部分集合Aに対して， |NG’’(A)|≧|NG(A∪V1’)|-|V2’|≧(|A|+|V1’|)-|V2’|=|A| よってG’’に対して帰納法の仮定を適用することで V1’’からV2’’への完全マッチングM2が存在することが分かる． M1∪M2がV1からV2への完全マッチングとなる．提出課題13 問1（ハーレム問題）： Bは男性の集合とし，Bの各男性は2人以上の恋人と結婚したいとする．この問題に解があるための必要十分条件を見つけよ．提出課題13 問1のヒント：・ 2部グラフG(V1,V2)に置き換えて考える．（V1が男性の集合）・必要十分条件は V1の任意の部分集合Aに対して，|NG(A)|≧2|A| ・必要性は簡単に分かる・十分性の証明にホールの結婚定理を用いる・ V1の各頂点を2個の独立点に分ける（∴ V1のコピーV1’を考える）・ |NG’(A)|=|NG(A’)|≧2|A’|≧|A|