Maximales Matching - Satz von König

Bipartit:
Konstuktion einer Zerlegung V = S [ T
durch Markierung der Knoten eines zusammenhängenden
(ungerichteten) Graphen:
1. Markiere einen (beliebigen) Startknoten mit s.
2. Markiere alle Nachbarknoten des Startknotens mit t.
3. Markiere alle noch unmarkierten Knoten, die einen mit t
markierten Nachbarknoten haben, mit s, sowie alle noch
unmarkierten Knoten, die einen mit s markierten
Nachbarknoten haben, mit t.
4. Wiederhole Schritt 3 so lange, bis entweder
I alle Knoten markiert sind oder
I zwei benachbarte Knoten die gleiche Markierung haben.
In diesem Fall ist der Graph nicht bipartit und der
Algorithmus kann abgebrochen werden.