研究内容:組合せ構造の表現法

マッチング

 n人の男性とn人の女性が存在し、全員が異性に対して好みの順番で並んでいる希望リストを持っている。男女を一人ずつ、n組のペアに分けた集合をマッチングという。

 この時、ある男性mと女性wのペアがマッチング中に存在せず、mとwが現在組んでいるペアの相手よりもお互いの希望リストでの順位が高いとき、このmとwのペア(m,w)をブロッキングペアという。ブロッキングペアが存在しないマッチングを安定マッチングといい、安定結婚問題ではこの安定マッチングを求める。

ページのトップへ戻る