Proposition - Erweiterung eines Matchings durch augmentierenden Weg

• Involvierte Definitionen:
  • Augmentierender Pfad
  • Matching
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Proposition: Erweiterung eines Matchings durch augmentierenden Weg

Sei ein Graph.
Sei ein Matching von .
Sei ein augmentierender Pfad.

Es bezeichne die gematchten Kanten, die auf liegen.

Es bezeichne die ungematchten Kanten, die auf liegen.

Wir enthalten ein neues Matching , wie folgt:

Für dieses Matching gilt weiter:

Anmerkung