Definition - Gematchte Knoten

• Konstrukte:
  • Perfektes Matching
• Involvierte Definitionen:
  • Graph
  • Matching
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Gematchte Knoten

Sei ein Graph.
Sei ein Matching von .

• Zwei Knoten heißen gematcht, wenn es eine Kante in dem Matching gibt, die und miteinander verbindet.
• Zwei Knoten heißen ungematcht, wenn es keine Kante in dem Matching gibt, die und miteinander verbinden würde.