Kolorowanie Grafów: Pościg za Liczbą Chromatyczną z Heurystykami

Koloryzacja grafu tak, aby żaden brzeg nie był monochromatyczny

Odpowiednia koloryzacja grafu przypisuje każdej wierzchołce kolor tak, że żadne dwie wierzchołki połączone brzegiem nie mają tego samego koloru. Najmniejsza liczba kolorów, która to umożliwia dla danego grafu, to jego liczba chromatyczna, oznaczana χ(G). Koloryzacja grafów wydaje się abstrakcyjna, ale jest w rzeczywistości podstawową operacją planowania: wierzchołki to egzaminy, zadania lub kanały radiowe, brzegami są konflikty, a odpowiednia koloryzacja to bezkonfliktowe przypisanie - harmonogramowanie egzaminów, alokacja rejestrów w kompilatorach i przydział częstotliwości bezprzewodowych jest wszystkim koloryzacją grafów w różnych strojach.

Dlaczego znalezienie χ(G) dokładnie jest trudne

Decydowanie, czy graf może być skolorowany z k kolorami, to problem NP-złożony dla każdego k ≥ 3 – nie istnieje znany algorytm, który rozwiązuje go w czasie wielomianowym dla wszystkich grafów, a większość informatyków uważa, że takiego algorytmu nie ma. Dlatego też każde praktyczne narzędzie do kolorowania używa heurystyki: kolejności punktów wierzchołowych do pokolorowania oraz reguły, która kolor nadać, które generuje dobre kolorowanie szybko bez jakiejkolwiek gwarancji optymalności.

Złoty podział i dlaczego kolejność ma znaczenie

Najprostsza heurystyka odwiedza wierzchołki w jakiejś kolejności i przypisuje każdemu najmniejszy numer kolor nie używany przez sąsiednie, już pokolorowane wierzchołki:

dla v w kolejności_wierzchołków: zastosowane = kolory sąsiednich wierzchołków pokolorowanych przez v color[v] = najmniejszy kolor nie występujący w zastosowanych To zawsze kończy się i używa maksymalnie Δ+1 kolorów, gdzie Δ jest największą liczbą stopni grafu – gwarantowany prawdziwy limit. Jednak kolejność podawana ma ogromne znaczenie: źle dobrana kolejność może zmusić regułę greedy do użycia znacznie więcej kolorów niż potrzeba w grafie, który mógłby być pokolorowany z bardzo niewielką liczbą kolorów, a dobrze dobrana kolejność może osiągnąć optimum. Dlatego złoty podział sam w sobie nie jest jednym algorytmem, to rodzina algorytmów rozróżniona całkowicie ze względu na strategię kolejności.

for v in vertex_order:
  used = colors of v's already-colored neighbours
  color[v] = smallest color not in used

Welsh-Powell: kolejność według stopnia

Heurystyka Welsh-Powella (1967) sortuje wierzchołki według malejącego stopnia przed uruchomieniem algorytmu greedy, z założenia, że wierzchołki o wysokiej gęstości połączeń mają najwięcej ograniczeń i powinny być kolorowane jako pierwsze, a dostępnych jest najmniej możliwości wyboru koloru. Jest prosta, szybka i zauważalnie lepsza niż losowa lub arbitralna kolejność wierzchołków na większości rzeczywistych grafów, choć nadal nie gwarantuje jej optymalności w najgorszym przypadku.

DSatur: sortowanie według nasycenia, dynamicznie

DSatur (Brélaz, 1979) ulepsza sortowanie zaproponowane przez Welsh-Powella poprzez ponowne obliczanie kolejności w trakcie procesu. W każdym kroku koloruje się nieobarwiony wierzchołek o najwyższym stopniu nasycenia – czyli z uwzględnieniem liczby użytych już odrębnych kolorów wśród jego sąsiadów – a w przypadku remisu, decyduje kolejność według stopnia. Adaptuje się to do bieżącego procesu barwienia, zamiast narzucać stały porządek z góry, i jest udowodniona jego optymalność dla wielu ważnych rodzin grafów, w tym grafów dwuróżnicowych. Na ogólnych grafach nie gwarantuje optymalności, ale w praktyce konsekwentnie przewyższa statyczne algorytmy greedy i Welsh-Powella, dlatego jest domyślnym heurystyką w większości współczesnych narzędzi do barwienia.

Jak blisko jest blisko na tyle?

Dla wielu rzeczywistych grafów, zwłaszcza tych rzadkich lub strukturalnych, DSatur trafia na prawdziwy współczynnik kolorowania lub znajduje się w odległości jednego koloru od niego. Najtrudniejsze przypadki to gęste, nieregularne grafy bez oczywistej struktury do wykorzystania, gdzie nawet DSatur może popaść w kilka kolorów powyżej χ(G) i tylko dokładne przeszukiwanie (metoda podziałowo-zyskowna lub programowanie całkowite) może potwierdzić minimalną wartość – co wiąże się z kosztem obliczeniowym rosnącym wykładniczo wraz ze wzrostem rozmiaru grafu. Jest to praktyczny kompromis, jaki czyni każde heurystyka kolorowania: DSatur oferuje niewielki, zwykle niewidoczny próg powyżej optimum, w zamian za czas działania skalujący się do grafów z milionami wierzchołków, gdzie dokładne rozwiązania nie są możliwe.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Graph Coloring i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.