Definition - Bipartiter Graph

• Beispiele:
  • Stabile Hochzeit
• Eigenschaften:
  • In bipartiten Graphen liegen die Endpunkte eines augmentierenden Pfades in unterschiedlichen Farbklassen
  • Heiratssatz von Frobenius
  • Heiratssatz von Hall
• Hinreichende Aussagen:
  • Bestimmung bipartiter Graphen
  • Proposition - Graph ist bipartit genau dann wenn er keinen Kreis ungerader Länge aufweist
• Charakterisierungen:
  • Proposition - Graph ist bipartit genau dann wenn er keinen Kreis ungerader Länge aufweist
• Involvierte Definitionen:
  • Graph
  • Knotenmenge
  • Teilmenge
  • Disjunktheit von Mengen
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Bipartiter Graph

Sei ein Graph.

Falls es gibt, sodass

• und

Wenn außerdem alle Kanten von nach führen, dann nennen wir bipartit.

und bezeichnen wir als Farbklassen von .

Anmerkung