Theorem - Heiratssatz von Frobenius

• Generalisierungen: Heiratssatz von Hall
• Involvierte Definitionen:
  • Bipartiter Graph
  • Farbklasse
  • Perfektes Matching
  • Nachbarschaft von Knotenmengen
• Veranstaltung:
  • AlMa
• Referenz: @herzogWiSe22

⠀

Theorem: Heiratssatz von Frobenius

Sei ein bipartiter Graph.
Seien die Farbklassen von .

Dann gilt nach dem Heiratssatz von Frobenius:

besitzt ein perfektes Matching

Anmerkung

Austauschbarkeit von und

In der zweiten Bedingung können wir auch durch austauschen.

Tipp

Ist falsch, dann kann es nicht genug “Ziele” für die Matching Kanten geben.

Damit wird der Heiratssatz von Frobenius gerne genutzt um zu zeigen, dass es kein perfektes Matching geben kann. Hierfür müssen wir nämlich nur eine Teilmenge finden, die die Bedingung verletzt.