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:
- Alle Kanten sind ungefärbt.
- Alle Knoten sind unmarkiert.
- Die Wurzel sei als außen markiert.
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:
- y ist markiert: Färbe (x,y) blau, d.h. als nicht im Baum enthalten
- y ist markiert: Färbe (x,y) rot, d.h. als im Baum enthalten.
- Falls y frei ist, haben wir einen erweiternden Weg gefunden.
- Falls y belegt ist, färbe die eindeutig best. Matchingkante (y,z)
rot, markiere y ``innen'' und z ``außen''.
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 G hat erweiternden Weg.