Tomas Oberhuber's Homepage

Algoritmus obarvování grafu lze implementovat jako standardní prohledavání do hloubky. Vstupem do algoritmu je graf a posloupnost vrcholů, která určuje pořadí, ve kterém je vrcholům přiřazována barva. Uspořádání této posloupnosti má zásadní vliv na rychlost algoritmu – osvědčené je například sestupné uspořádání podle stupně vrcholu.

Sekvenční algoritmus pracuje takto: Vezme první vrchol z posloupnosti, přiřadí mu nejnižší možné číslo TeX Embedding failed! (k je počet barev k dispozici) takové, že žádný sousední vrchol není obarven číslem TeX Embedding failed!. Potom stejný postup provede postupně se všemi následujícími vrcholy. Podaří-li se obarvit poslední vrchol, algoritmus úspěšně skončí. Pokud se nějaký vrchol nedá obarvit (všech k barev je použito sousedními vrcholy), algoritmus se vrátí k předchozímu vrcholu v posloupnosti a obarví ho následující nejnižší barvou.

Příklad: Obarvení grafu třemi barvami

Graf

Stavový strom

Pokud se bude stavový strom prohledávat do hloubky, výsledné obarvení bude
(vrchol-barva): 1-1, 3-2, 4-3, 2-2. Všimněte si, že pokud by algoritmus vzal jako vstupní posloupnost 2, 3, 4, 1 a obarvil tyto vrcholy následovně: 2-1, 3-2, 4-3, potom by vrcholu 1 nemohl přiřadit barvu a tento podstrom by prohledával zbytečně. U velkých grafů je seřazení posloupnosti velmi důležité.