安定結婚問題「絶望の定理」の紹介 - Qiita

はじめに この記事では巷で絶望の定理1と呼ばれている定理の紹介を行っていきます。 絶望の定理は安定結婚問題というグラフ理論の問題における定理です。"絶望"という名前のインパクトでときどき話題になっているよう。 → 「数学の定理No.1決定戦」高校数学の美しい物語 定理の名前だけが独り歩きして日本語での解説があまりないように思ったので、研究していた頃の記憶をたどりながらご紹介しようと思います。 2020/3/15 追記： 絶望の定理の証明をこちらの記事にまとめました！ 安定結婚問題「絶望の定理」の証明 絶望の定理とは？ 安定マッチングと駆け落ちペア 絶望の定理とは、ある安定マッチングに入れなかった人間は、すべての安定マッチングに入ることができないという定理です。 安定マッチングとは駆け落ちするペアが存在しないマッチングのことです。 男女3対3の合コンを例にとって説明します。下の図を見てくださ