Greedy-Algorithmus zur Graphenfärbung

while (nicht alle Knoten gefärbt) {
    x = irgendein nicht gefärbter Knoten;
    M = Menge der Farben der Nachbarn von x;
    x erhält kleinste Farbe, die nicht in M ist;
}


Aufgabe:

Finde Beispiele (d. h. Graph mit Knotenreihenfolge), für die der Algorithmus keine optimale Färbung findet. Wie groß kann die Abweichung (= Anzahl der unnötig benutzten Farben) werden?



Johannes Waldmann 2005-01-25