Definition - Farbklasse

• Eigenschaften:
  • In bipartiten Graphen liegen die Endpunkte eines augmentierenden Pfades in unterschiedlichen Farbklassen
• Involvierte Definitionen:
  • Bipartiter Graph
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Farbklasse

Sei ein bipartiter Graph.

Dann gibt es , sodass

• und

Dann bezeichnen wir als Farbklassen von .

Anmerkung

Tipp

Zur Bestimmung der Farbklassen, siehe Algorithmen zur Herleitung bipartiter Graphen 😉