グラフ理論において、安定結婚問題があります。
ある2部グラフの特定の安定マッチングにおいて、ペアを作れなかった人(たとえば男性数>女性数でのマッチングで存在)は、どのような安定マッチングにおいてもペアが作れないことを、安定結婚問題における「絶望の定理」と呼ぶらしいのですが、この定理の証明を見つけられずにいます。
証明自体、もしくは証明のソースをご存知の方はいらっしゃいますでしょうか。
グラフ理論において、安定結婚問題があります。
ある2部グラフの特定の安定マッチングにおいて、ペアを作れなかった人(たとえば男性数>女性数でのマッチングで存在)は、どのような安定マッチングにおいてもペアが作れないことを、安定結婚問題における「絶望の定理」と呼ぶらしいのですが、この定理の証明を見つけられずにいます。
証明自体、もしくは証明のソースをご存知の方はいらっしゃいますでしょうか。
@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 の3つの間で、パートナーの有無は、単調増加(語弊あり?)する
2. ある参加者のパートナーの有無が stable matching 間で変わったとすると、1. の結果から玉突き事故のようなことが起こってしまうので、そんなことは起こらない)
によって、説明できそうでした。
Rural Hospital Theorem
と呼ばれているものではないでしょうか? この記事で確認してみて下さい。安定マッチングのおはなし