Kolorowanie grafu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu teoria grafów.




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem marszrutyzacji
problem kojarzenia małżeństw


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


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.

Podstawowe definicje[edytuj | edytuj kod]

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 G nazywamy liczbę \! \chi(G) równą najmniejszej możliwej liczbie kolorów potrzebnych do legalnego pokolorowania wierzchołków grafu G.

Algorytmy kolorowania grafów[edytuj | edytuj kod]

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 | edytuj kod]

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 P_6.

Algorytm SL (smallest last)[edytuj | edytuj kod]

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 O(n+m), gdzie n - liczba wierzchołków, m - liczba krawędzi.

Algorytm SLF (saturated largest first)[edytuj | edytuj kod]

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 O(m \log n).

Inne warianty kolorowania grafów[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]

Wikimedia Commons

Bibliografia[edytuj | edytuj kod]

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