Algorytm udoskonalania kolorów

W teorii grafów i informatyce teoretycznej algorytm udoskonalania kolorów znany również jako naiwna klasyfikacja wierzchołków lub jednowymiarowa wersja algorytmu Weisfeilera-Lemana jest procedurą używaną do testowania, czy dwa grafy są izomorficzne , czy nie.

Opis

Definiujemy sekwencję kolorowania wierzchołków zdefiniowaną w następujący sposób: ${\ displaystyle cr ^ {t}}$

• ${\ displaystyle cr ^ {0}}$ to początkowe zabarwienie. $Jeśli$ wykres nie $,$ każdemu kolor Jeśli wykres jest oznaczony, to etykieta wierzchołka jest do $}$$displaystyle cr ^ {0} (v)$ .
• dla wszystkich wierzchołków ${$ do ${\$ . Innymi słowy, nowy kolor wierzchołka $wielozbioru$ para utworzona z poprzedniego koloru i kolorów jego sąsiadów.

Algorytm ten stale udoskonala obecną kolorystykę. W $nie$ , przed n krokami, gdzie n jest liczbą wierzchołków, stabilizuje się: się już, gdy t wzrasta. To ostateczne zabarwienie nazywa się zabarwieniem stabilnym .

Ekspresyjność

Algorytm ten nie rozróżnia cyklu o długości 6 od pary trójkątów (przykład V.1 w ).

Złożoność

Stabilne kolorowanie można obliczyć w postaci O((n+m)log n), gdzie n to liczba wierzchołków, a m to liczba krawędzi. Udowodniono, że ta złożoność jest optymalna dla niektórych klas grafów.