Definition - Maximales Matching

• Generalisierungen:
  • Matching
• Eigenschaften:
• Charakterisierungen:
  • Proposition - Matching ist maximal gdw Matching enthält keine augmentierenden Pfade
  • Satz von König
• Involvierte Definitionen:
  • Matching
  • Graph
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Maximales Matching

Sei ein Graph.
Sei ein Matching von .

Wir bezeichnen als maximales Matching von , wenn es die maximal mögliche Anzahl von Kanten enthält, es also kein Matching mit mehr Kanten geben kann:

Wobei Matchings von bezeichne.