Es seien eine Anzahl $n$ von Ländern und dazugehörige Landkarte als Matrix Adjazenzmatrix[][] gegeben, in der Adjazenzmatrix[j]=true, wenn die
Länder i und j Nachbarn sind, andernfalls Adjazenzmatrix[j]=false. Unser Ziel, die Karte mit einer minimalen Anzahl von Farben einzufärben, wobei
zwei Länder, die aneinander grenzen, unterschiedliche Farben haben müssen. Das Problem löst man optimal mit Hilfe der Backtracking--Methode, aber der
Algorithmus hat exponentielle Laufzeit. Eine Greedy-Methode liefert zwar eine akzeptable Anzahl von
Farben, aber nicht immer die minimale Anzahl. Wir färben das erste Land mit 0 und dann sukzessive alle Länder
mit der ersten verfügbaren Farbe,wobei gilt: Es darf keine gleichfarbigen Nachbarländer geben. Stundenplanprobleme lassen sich als Graphfärbungsprobleme formulieren: Die
Knoten des Graphen sind dabei die zu platzierenden Veranstaltungen, und eine Kante wird zwischen zwei Veranstaltungen eingefügt, die nicht
gleichzeitig stattfinden können.