Marriage Theorem
のステートメント
- 定理（P. Hall, 1935）
- 有限個の点からなる二つの（共通の点を持たない）集合AとBがあり、
Aの点とBの点の間に線が何本か引かれている状況を考える。
ここで、Aの全ての点ごとに、そこから出ている線を一本ずつ選んで、
相手側のBの点が選んだ線ごとに全て異なるようにできるための必要充分条件を考える。
その必要充分条件は、Aの点たち（何個でもよい）をどのように選んでも、
そのどれかと結ばれているBの点の総数が、
初めに選んだAの点の個数以上になることである。
何故Marriage Theorem
と名付けられたのか気になる方は、
線で結ばれた2点を「互いに好意を持っている」、
線を選ぶくだりを「カップルを作る」と読み替えて下さいませ。
トップページへ戻る
(c) Koji NUIDA 2005: All rights are reserved.