Definition - Stabile Hochzeit

• Hinreichende Aussagen:
  • Gale-Shapley Algorithmus (Men propose - Women dispose)
• Involvierte Definitionen:
  • Bipartiter Graph
  • Perfektes Matching
  • Totalordnung
• Veranstaltung: AlMa
• Referenz:
  • @herzogWiSe22
  • @hochstaettlerWiSe22

⠀

Definition: Stabile Hochzeit (Stable Matching Problem)

Sei eine Menge von Männern.
Sei eine Menge von Frauen.

• Jeder Mann habe eine Präferenzliste, die durch die Totalordnung auf gegeben sei.
• Jede Frau habe eine Präferenzliste, die durch die Totalordnung auf gegeben sei.

Wir bezeichnen als stabile Hochzeit, wenn

Das heißt:

• und sind verpaart
• oder zieht seine Partnerin der Frau vor
• oder zieht seinen Partner dem Mann vor