Kolorowanie grafu polega na przyporządkowaniu koloru każdemu węzłowi w grafie przy wykorzystaniu jak najmniejszej liczby kolorów(liczby chromatycznej). Jednakże przy założeniu, że dwa różne ale przyległe do siebie węzły nie będą miały tego samego koloru. Takie kolorowanie stosuje się często na mapach do oznaczenia terenów lub do określenia jak składować chemikalia bo jak wiadomo niektóre substancje po zetknięciu się ze sobą mogą spowodować eksplozje.

Algorytm działa w następujący sposób:

G-Graf;
nowy_kolor - zbiór kolorów użytych;
kolor=0;

Dopóki istnieją nie pokolorowane wierzchołki w G to
{
  nowy_kolor = pusty;
  kolor = kolor+1;
  V = pierwszy nie pokolorowany wierzchołek w G;
  Dopóki V nie jest puste to
  {
    jest_p = fałsz;
    W = pierwszy wierzchołek w zbiorze nowy_kolor;
    Dopóki W nie jest puste to
    {
      Jeżeli istnieje krawędź pomiędzy V i W w G to
      {
        jest_p = prawda;
      }
      W = następny wierzchołek w zbiorze nowy_kolor;
    }
    Jeżeli jest_p=fałsz to
    {
      oznacz V jako pokolorowany kolorem kolor;
      dołącz V do zbioru nowy_kolor;
    }
    V = następny nie pokolorowany wierzchołek w G;
  }
}


Przykład działania algorytmu:

Komentarze