2014/11/08

Hallの結婚定理とその証明

分野: グラフ理論  レベル: マニアック

Hall(ホール)の結婚定理:頂点集合が $U,\:V$ と分割された二部グラフ $G$ に対して,以下は同値。
条件1:$U$ の頂点を全てカバーするマッチングが存在する
条件2(Hallの条件):任意の $U$ の部分集合 $A$ に対して,$|A|\leq |\Gamma(A)|$

ただし,$\Gamma(A)$ は $A$ と辺でつながっている頂点の集合。


ホールの定理,結婚定理とも。グラフ理論の言葉で書くと一見分かりにくいですが,意味が理解できると非常に面白い定理です。

マッチングとは

まず,条件1を理解するためにマッチングについて説明します。
(追記:二部グラフの最大マッチングと増加道
マッチングとは端点がかぶらないように辺をいくつか取ってきたものです。また,マッチングの端点に属する頂点を「マッチングでカバーされている」と言います。

Hallの定理

例えば,図では緑の辺がマッチングの一例です。頂点集合 $U$ の中で上三つはカバーされていますが,一番下はカバーされていません。 $V$ は全てカバーされています。

$U$ の各頂点を男性,$V$ の各頂点を女性,男性 $a$ が女性 $b$ とお互いに結婚してもよいと思うとき$(a,b)$ に辺を引いたグラフを考えてみます。このときマッチングは結婚成立の一例を表しています。

すなわち条件1は,「うまいマッチングを選べば男がみんな結婚できる」という条件になります。

結婚条件(Hallの条件)について

次は条件2について説明します。 $U$ の部分集合 $A$ に対して,$\Gamma(A)$ とは $A$ と辺でつながっている頂点の集合で、 $V$ の部分集合です。
例えば,図において $\Gamma\{2\}=\{7\},\:\Gamma\{1,2,3\}=\{5,7\}$ などです。

ホールの定理

日本語で言うと,男を適当に何人か選んだとき,その男たちと結婚しうる女性を寄せ集めてきた集合です。

すなわち条件2は「男を適当に何人か選んでくると,その男たちと結婚しうる女性の人数の方が多い」という条件になります。

例えば,図では $A=\{1,2,3\}$ とすると $|A| =3 > 2= |\Gamma (A)|$ となっているのでHallの条件を満たしていません。これでは $\{1,2,3\}$ の誰かは明らかに結婚できません。

ここまで理解できればHallの定理における「条件1→条件2」は簡単に証明できます。

証明

対偶を示す。条件2が成立しないとき,ある $U$ の部分集合 $A$ が存在して,$|A| > |\Gamma(A)|$ となる。
よって,$A$ をカバーするようなマッチングは存在せず,条件1は成り立たない。

つまり,Hallの条件は $U$ をカバーするマッチングが存在するための必要条件というわけです。実はこれが十分条件にもなっているというのがHallの結婚定理の偉大なところです。驚きですね!

Hallの結婚定理の証明

それではいよいよ難しい方:「条件2→条件1」を帰納法で証明します。少し長いですが見かけほど難しくありません。

証明

$|U|$ に関する帰納法で証明する。 $|U|=1$ のときは自明。

$|U|\leq k$ のときにHallの結婚定理が成立すると仮定する。 $|U|=k+1$ でありHallの条件を満たすグラフ $G$ でを考える。以下二通りに場合分け。

・ $U$ の任意の真部分集合 $A$ に対して $|A|+1\leq |\Gamma(A)|$ となる場合。
このときは余裕があるので,適当に辺$(u,v)$ を一本選べばよい。そして,頂点 $u$ と $v$ を除いた二部グラフ $G'(U’,V’)$ を考えると,$G’$においてもHallの条件を満たしている。よって,帰納法の仮定により $U’$をカバーするマッチング $M$ が存在する。全体のマッチングとして $M$ と$(u,v)$ の和集合を持ってくればよい。

・ $|A|=|\Gamma(A)|$ を満たす $U$ の真部分集合 $A$ が存在する場合。
$G$ がHallの条件を満たしていることと帰納法の仮定により,頂点 $A$ をカバーするマッチング $M_1$ が存在する。そして,そのマッチングは $A$ と $\Gamma(A)$ の間の完全マッチング(全頂点をカバーするマッチング)である。
よって,残ったグラフ $G'(U’,V’)$ に $U’$をカバーするマッチング $M_2$ が存在することを証明すればよい。

ホールの結婚定理の証明

ここで,$U’$の部分集合 $B$ を考えてみると,$G$ がHallの条件を満たしていることから $|A\cup B|\leq |\Gamma(A\cup B)|$ である。よって,$A\cup B$ の行き先で $\Gamma(A)$ に属さないものが少なくとも $|B|$ 個は存在する。それらは $A$ とはつながっていないので,全て $B$ とつながっている。すなわち,$|\Gamma (B)|\geq |B|$ 。よって. $G’$もHallの条件を満たすので帰納法の仮定により $U’$をカバーするマッチング $M_2$ が存在する。


ちなみに,マッチングは二部グラフ以外の一般のグラフでも考えることができます。一般グラフではHallの定理の拡張としてTutteの定理というものがあります。

マッチングの理論は非常に美しいです。最高です。
分野: グラフ理論  レベル: マニアック