Definition - Augmentierender Pfad

• Generalisierungen:
  • Alternierender Pfad
• Eigenschaften:
  • Erweiterung eines Matchings durch augmentierenden Weg
  • Proposition - Matching ist maximal gdw Matching enthält keine augmentierenden Pfade
• Hinreichende Aussagen:
  • In bipartiten Graphen liegen die Endpunkte eines augmentierenden Pfades in unterschiedlichen Farbklassen
  • Augmentierende Pfade haben stets eine ungerade Länge
  • Augmentierende Pfade haben stets eine gerade Knotenanzahl
• Involvierte Definitionen:
  • Weg
  • Graph
  • Ungematchte Knoten
  • Matching
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Augmentierender Pfad

Sei ein Graph.
Sei ein Matching von .

Sei ein alternierender Pfad. Sind darüber hinaus der Anfangs- und Endknoten und ungematcht, so bezeichnen wir als augmentierenden Weg.