Definition - Matching

• Typen:
  • Perfektes Matching
  • Maximales Matching
• Konstrukte:
  • Gematchte Knoten
  • Ungematchte Knoten
  • Alternierender Pfad
  • Augmentierender Pfad
• Eigenschaften:
  • Erweiterung eines Matchings durch augmentierenden Weg
  • Proposition - Matching ist maximal gdw Matching enthält keine augmentierenden Pfade
  • Satz von König
• Hinreichende Aussagen:
  • Heiratssatz von Hall
• Involvierte Definitionen:
  • Teilmenge
  • Graph
  • Inzidenz
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Matching

Sei ein Graph.

Die Kantenmenge bezeichnen wir als Matching von , falls sie keine Kanten enthält, die zueinander inzident sind.

Das heißt: Alle Knoten werden von höchstens einer Kante des Matchings getroffen.

(Dabei darf es natürlich auch Knoten geben, die von gar keiner Kante getroffen werden.)