ここから本文です

グラフ理論のHallの結婚定理について質問です。証明の仕方や過程がよくわかりませ...

xsh********さん

2008/10/1418:25:29

グラフ理論のHallの結婚定理について質問です。証明の仕方や過程がよくわかりません。

数学的帰納法を使って証明するようなのですが、いまいちよく解りません。証明方法を教えてください。証明の方針や過程を詳しく教えていただけると非常に助かります。

閲覧数:
2,398
回答数:
1
お礼:
250枚

違反報告

ベストアンサーに選ばれた回答

lan********さん

編集あり2008/10/1609:11:02

現実的な意味合いとしては「結婚するなら見知った人と」
が実現する条件は?という内容です。

Hall の結婚定理の意味する内容を数学的に定式化します。
n 個の元 f_1, f_2, ... , f_n を持つ有限集合 V と、
r 個の元 m_1, m_2, ... , m_r を持つ有限集合 W があるとします。

V の各元 f_i (i=1, 2, ... , n) に、W の空でない部分集合 S_i
が対応し、各 f_i は S_i の元の 1 つと辺で結ぶことが目的です。
このとき以下のルールを満たすか?を考えます。

(ルール)異なる f_i, f_j (i≠j) が同じ m_k と辺で結ばれることはない。

ルールを満たす辺の結び方が可能なことを
「完全マッチングが存在する」と表現します。

V の元と W の元を辺で結ぶことを『結婚』と呼んでいて、
ルールは重婚を禁止するものです。V を例えばある女性の集合、
W をある男性の集合、S_i を女性 f_i の知り合いの集合とすると、
V に属する女性全員が知り合いの男性と結婚できるための条件が
Hall の定理の内容です。

例として、V={f_1, f_2}, W={m_1, m_2, m_3} で、
S_1=S_2={m_1} のとき、f_1, f_2 それぞれ m_1 としか
辺を結び得ないので、ルールは満たし得ません。
一方、S_1={m_1, m_2}, S_2={m_1, m_3} ならば、
f_1 と m_1 が結ばれたとしても、f_2 を m_3 と結べばいい
ので、いつでもルールを満たし得ます。

以上の前提で、以下が Hall の定理です。

[Hall の定理] 完全マッチングが存在する必要十分条件は、
V の任意の部分集合 X を取ってきて、その元の数が p のとき、
"X に属する f_i に対応する S_i の和集合" の元の数は p 以上。

注意点として、この条件は V の "全ての" 部分集合で成り立つ
べきなのです。例えば上記の例をもう一度用いると、
V={f_1, f_2}, W={m_1, m_2, m_3} で、
S_1=S_2={m_1} のとき、X={f_1} や X={f_2} のときは
p=1 で条件を満たすけど、X=V={f_1, f_2} のときは
p=2 なのに S_1∪S_2={m_1} の元の数は 1 なので
条件を満たしません。実際、完全マッチングが存在しません。

[Hall の定理の証明]
(必要性)これはほぼ明らか。
つまり、異なる p 人の女性の結婚相手として、異なる p 人
の男性が必要、ということ。

(十分性)証明の肝の部分です。
条件を満たしたところで、実際に組み合せられるか?は
別問題です。本当にそれができることを示すべきです。

V の元の数 n についての数学的帰納法で示す。
(1) n=1 のとき 少なくとも 1 人の相手が必要なので明らか。
(2) n-1 以下で正しいと仮定して、n の時を示す。

2 通りの場合分けで示す。

(2-a) V の任意の部分集合 X の元の数が 1 ≦ p ≦ n-1 のとき、
"X に属する f_i に対応する S_i の和集合" の元の数は p+1 以上とする。

このとき、V のある 1 つ(例えば f_1)をマッチングさせた
(S_1 のある元と辺で結ぶ)としても、それを除いた集合で
条件を満たすので、帰納法の仮定より完全マッチングが存在する。

(2-b) 条件を満たす範囲での (2-a) の否定命題は、
「V のある部分集合 X が存在して、その元の数が 1 ≦ p ≦ n-1 で、
"X に属する f_i に対応する S_i の和集合" の元の数は丁度 p 」
これを仮定する。

T=S_1∪S_2∪…∪S_n,
Y を、X に属する f_i に対応する S_i の和集合、とおく。

このとき仮定より、
T の元の数は n 以上、Y の元の数は p なので、
T - Y(T から Y を除いた集合)の元の数は (n-p) 以上。

"W-X に属する f_i に対応する S_i の和集合" は T-Y を含むので、
X と Y をマッチングさせ、W-X と T-Y をマッチングさせればよい。
それぞれ帰納法の仮定を満たしているので、完全マッチング
が存在する。(証明終)

面白い帰納法の適用方法だと思います。

この質問は投票によってベストアンサーに選ばれました!

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる