Zurückblättern Weiterblättern Übergeordnetes Thema Sachgebiet Hauptinhaltsverzeichnis Stichwortverzeichnis Hilfeseiten        


Alternierende Wege, Satz von Berge


1. Alternierende Wege: Es sei ein Graph mit einem Matching . Ein Weg in wird alternierend genannt, wenn in auf jede Kante mit (bzw. ) eine Kante mit (bzw. ) folgt.
Ein offener alternierender Weg wird zunehmend genannt, wenn kein Endpunkt des Weges mit einer Kante aus inzidiert.
2. Satz von Berge:
a) Ein Matching in einem Graphen ist genau dann maximal, wenn es in keinen zunehmenden alternierenden Weg gibt.
b) Ist ein zunehmender alternierender Weg in mit zugehöriger Menge durchlaufener Kanten, dann bildet ein Matching in mit .

Man spricht in diesem Zusammenhang von einem Austauschverfahren .

Beispiel

Im Graphen der folgenden Abbildung ist ein zunehmender alternierender Weg bezüglich des Matchings Mit dem Austauschverfahren erhält man daraus das Matching