10.3 Erweiternder Weg

Ein erweiternder Weg in G bzgl. M ist eine Folge von Kanten, die bei einem freien Knoten beginnt, bei einem anderen freien Knoten endet und abwechselnd Matching- und Nichtmatchingkanten benutzt.

Beispiel:

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:

M ist Maximum Matching $\iff$ Es gibt keinen erweiternden Weg bzgl. M .

Beweis:

$$\Rightarrow$$ trivial!

$$\Leftarrow$$ 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 := $\emptyset$ ;
     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: