prev up inhalt next


10.4 (Erweiternder) alternierender Baum

Die Wurzel dieses alternierenden Baumes bildet einer der freien Knoten x aus G . Alle Wege von x ausgehend sind alternierend, d.h. sie benutzen abwechselnd Nichtmatching- bzw. Matchingkanten. Die Wurzel heißt außen, die Nachfolger von außen nennen wir innen, deren Nachfolger wiederum außen usw.


Beispiel:



Zu Beginn gilt nun:

Wähle nun eine ungefärbte Kante (x,y) inzident zu einem ``außen''-Knoten x . Falls das nicht möglich ist, so gibt es keinen erweiternden Weg mehr zu finden. Gibt es jedoch eine solche Kante, so unterscheiden wir in zwei Fälle:

Durch diese Konstruktion ist es also möglich, erweiternde Wege in einem Graph G zu finden.

Sei G nun nicht bipartit.


Blüte (blossom) = Kreis ungerader Länge

Kante von ``außen'' nach ``außen'' ergibt Blüte. (Im bipartiten Graph nicht möglich.)

Es gilt folgender Satz:

G' hat erweiternden Weg $\iff$ G hat erweiternden Weg.


prev up inhalt next