Definition - Alternierender Pfad

• Konstrukte:
  • Augmentierender Pfad
• Generalisierungen:
  • Pfad
• Involvierte Definitionen:
  • Graph
  • Weg
  • Matching
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Alternierender Pfad

Sei ein Graph.
Sei ein Matching von .

Der Weg heißt alternierend, wenn die Kanten abwechselnd in dem Matching (also in ) und außerhalb des Matchings (also in ) liegen.