Alternierende Wege, Satz von Berge

1. Alternierende Wege:

Es sei G ein Graph mit einem Matching M. Ein Weg W in G wird alternierend genannt, wenn in W auf jede Kante e mit (bzw. ) eine Kante e' mit (bzw. ) folgt.
Ein offener alternierender Weg wird zunehmend genannt, wenn kein Endpunkt des Weges mit einer Kante aus M inzidiert.

2. Satz von Berge:

1. Ein Matching M in einem Graphen G ist genau dann maximal, wenn es in G keinen zunehmenden alternierenden Weg gibt.
2. Ist W ein zunehmender alternierender Weg in G mit zugehöriger Menge E(W) durchlaufener Kanten, dann bildet ein Matching in G mit .

Man spricht in diesem Zusammenhang von einem Austauschverfahren.

Beispiel

Im Graphen der folgenden Abbildung ist ({1,2},{2,3},{3,4}) ein zunehmender alternierender Weg bezüglich des Matchings Mit dem Austauschverfahren erhält man daraus das Matching