Es ist einleuchtend, daß sich ein Matching M entlang eines solchen erweiternden Weges um eine Kante erweitern läßt, indem man jede Matchingkante zu einer Nichtmatchingkante macht und umgekehrt. Dabei gilt der folgende Satz:
: | trivial! |
: | Es gibt keinen erweiternden Weg bzgl. M . |
Annahme: Es gibt M' mit |M'| > |M| . | |
Betracht nun M und M' in G und entferne alle Kanten, die sowohl in M als auch in M' enthalten sind. Da |M'| > |M| , gibt es eine Folge von Kanten aus dem Rest von G , die abwechselnd in M' und M liegen, wobei diese Folge mit einer Kante aus M' beginnt und aufhört. Die Endpunkte dieser Folge von Kanten sind also frei bzgl. M . Somit ist diese Folge von Kanten ein erweiternder Weg bzgl. M . Dies ist ein Widerspruch zur Voraussetzung |
Aus dieser Eigenschaft folgt ein neuer Ansatz zur Lösung des Problems, ein
Maximum Matching zu bestimmen:
M := ;
REPEAT
Finde einen erweiternden Weg bzgl. M;
Falls gefunden, erweitere M längs dieses Weges;
UNTIL kein erweiternder Weg vorhanden;
Ein noch ungeklärtes Problem bei diesem Algorithmus ist die Frage, wie man einen erweiternden Weg bzgl. eines Matchings findet. Die Antwort liegt in der Konstruktion eines (erweiternden) alternierenden Baumes: