Kolorowanie grafu

przypisywanie kolorów obiektom grafu zgodnie z narzuconymi regułami

Kolorowanie grafu polega w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego koloru[1].

Podstawowe definicje edytuj

Klasyczne (wierzchołkowe) kolorowanie grafu – przyporządkowywanie wierzchołkom grafu liczb naturalnych w taki sposób, aby końce żadnej krawędzi nie miały przypisanej tej samej liczby. Ze względów historycznych oraz dla lepszego zobrazowania problemu mówi się o kolorowaniu, przy czym różnym kolorom odpowiadają różne liczby.

Pokolorowaniem wierzchołków grafu nazywamy jedno konkretne przyporządkowanie kolorów wierzchołkom. Pokolorowanie jest legalne (dozwolone), gdy końcom żadnej krawędzi nie przyporządkowano tego samego koloru.

Optymalnym pokolorowaniem danego grafu nazywamy legalne pokolorowanie zawierające najmniejszą możliwą liczbę kolorów.

Liczbą chromatyczną grafu   nazywamy liczbę   równą najmniejszej możliwej liczbie kolorów potrzebnych do legalnego pokolorowania wierzchołków grafu  

Algorytmy kolorowania grafów edytuj

Ze względu na bardzo szerokie zastosowania, kolorowanie grafów jest przedmiotem rozległych badań. Problem znalezienia optymalnego pokolorowania, a także znalezienia liczby chromatycznej jest NP-trudny. Z tego względu do kolorowania dużych grafów nadają się jedynie algorytmy przybliżone.

Algorytm LF (largest first) edytuj

Kolorowanie grafu za pomocą algorytmu LF można opisać następująco:

  1. Uporządkuj wierzchołki grafu malejąco według ich stopni (liczby krawędzi z nich wychodzących).
  2. Koloruj wierzchołki zachłannie, zgodnie z ustaloną wcześniej kolejnością (zaczynając od wierzchołka o największym stopniu).

Algorytm LF jest algorytmem statycznym, gdyż raz ustalona kolejność wierzchołków nie zmienia się w trakcie jego działania. Najmniejszym dość trudnym grafem jest ścieżka  

Algorytm SL (smallest last) edytuj

Algorytm SL wygląda następująco:

  1. Znajdź wierzchołek o minimalnym stopniu i usuń go z grafu.
  2. Powtarzaj krok pierwszy tak długo, aż graf będzie pusty (zapamiętaj kolejność usuwanych wierzchołków).
  3. Koloruj wierzchołki zachłannie, zgodnie z ustaloną wcześniej kolejnością (zaczynając od wierzchołków usuniętych później).

Algorytm SL jest statyczny, jego złożoność wynosi   gdzie   – liczba wierzchołków,   – liczba krawędzi.

Algorytm SLF (saturated largest first) edytuj

Kolorowanie grafu przy pomocy algorytmu SLF polega na wykonaniu poniższych czynności:

dopóki istnieją niepokolorowane wierzchołki wykonuj operacje:
{
     znajdź wierzchołek o maksymalnym stopniu spośród wierzchołków o maksymalnym stopniu nasycenia
     pokoloruj znaleziony wierzchołek zachłannie
}

Stopniem nasycenia wierzchołka nazwiemy tu liczbę różnych kolorów sąsiednich z tym wierzchołkiem. Złożoność algorytmu SLF wynosi  

Inne warianty kolorowania grafów edytuj

Zobacz też edytuj

Przypisy edytuj

  1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 95. ISBN 0-387-95014-1.

Bibliografia edytuj

  • Marek Kubale i inni: Optymalizacja dyskretna. Modele i metody kolorowania grafów. WNT, 2002. ISBN 83-204-2747-9.