ホールの定理 論理的に等価な定理

ウィキペディア

ホールの定理

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

論理的に等価な定理

この定理は組合せ数学における非常に強力な一連の定理の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