14217


グラフ理論において、[安定結婚問題](https://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E7%B5%90%E5%A9%9A%E5%95%8F%E9%A1%8C)があります。

ある２部グラフの特定の安定マッチングにおいて、ペアを作れなかった人(たとえば男性数>女性数でのマッチングで存在)は、どのような安定マッチングにおいてもペアが作れないことを、安定結婚問題における「絶望の定理」と呼ぶらしいのですが、この定理の証明を見つけられずにいます。

証明自体、もしくは証明のソースをご存知の方はいらっしゃいますでしょうか。


CC BY-SA 3.0
2015-08-09T09:15:41.190
14205
2015-08-09T16:52:50.623
754
question
グラフ理論
安定結婚問題の「絶望の定理」の証明


@argus さんの情報を情報をもとに、調べて行った結果、

<https://cs.stackexchange.com/a/37942/37273>  
(man-oriented な Gale-Shapley で man-optimal (最大元)かつ woman-pessimal (最小元)が得られる)  
と  
<https://math.stackexchange.com/q/978729/260854>  
(1. optimal, 任意の matching, pessimal の３つの間で、パートナーの有無は、単調増加(語弊あり？)する  
2\. ある参加者のパートナーの有無が stable matching 間で変わったとすると、1.
の結果から玉突き事故のようなことが起こってしまうので、そんなことは起こらない)

によって、説明できそうでした。


CC BY-SA 3.0
2015-08-09T16:15:32.893
14217
2015-08-09T16:52:50.623
2017-04-13T12:48:38.993
-1
754
14205
answer