Ermittlung maximaler Matchings
Gegeben sei ein Graph 
mit einem Matching 
a) Man bilde zu 
ein gesättigtes Matching 
mit 
b) Man wähle in
einen Knoten 
der mit keiner Kante aus
inzidiert,
und suche in
einen zunehmenden alternierenden Weg, der in 
beginnt.
c) Existiert ein solcher Weg, dann liefert das oben beschriebene Austauschverfahren
ein Matching 
mit 
Existiert kein solcher Weg, dann lösche man in
den Knoten
und alle mit
inzidierenden Kanten und wiederhole Schritt b).
Es gibt einen kompliziert zu beschreibenden Algorithmus von EDMONDS, der sich zur
effektiven Suche nach maximalen Matchings eignet (s. Lit. 5.36).
