Proposition - Matching ist maximal gdw Matching enthält keine augmentierenden Pfade

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

⠀

Proposition: Matching ist maximal Matching enthält keine augmentierenden Pfade

Sei ein Graph.
Sei ein Matching von .

Dann gilt: