Algorytm kolorowania krawędzi Misry i Griesa

Algorytm kolorowania krawędzi Misry i Griesa to wielomianowy algorytm czasu w teorii grafów , który znajduje kolorowanie krawędzi dowolnego wykresu. $Wytworzone$ kolorowanie wykorzystuje co $.$ , gdzie maksymalnym stopniem Jest to optymalne dla niektórych wykresów, a zgodnie z twierdzeniem Vizinga wykorzystuje co najwyżej jeden kolor więcej niż optymalny dla wszystkich innych.

Po raz pierwszy został opublikowany przez Jayadeva Misrę i Davida Griesa w 1992 roku. Jest to uproszczenie wcześniejszego algorytmu autorstwa Béli Bollobása .

$,$ prawie optymalnym algorytmem do kolorowania krawędzi . Szybsza $_$ _ raport techniczny z 1985 r. sporządzony przez Gabow i in., ale nigdy nie został opublikowany.

Ogólnie rzecz biorąc, optymalne kolorowanie krawędzi jest NP-zupełne, więc jest bardzo mało prawdopodobne, aby istniał algorytm czasu wielomianowego. Istnieją jednak algorytmy kolorowania krawędzi z dokładnym czasem wykładniczym , które dają optymalne rozwiązanie.

Fani

Wachlarz F=[x_1,x_2,x_3] z v (przerywane krawędzie są bezbarwne), (v,x_1),(v,x_2),(v,x_3) to krawędzie wachlarzowe. F'=[x_1,x_2] również jest wachlarzem v, ale nie jest maksymalny.

kolor x krawędzi ( u, v ) jest wolny na u , jeśli c (u, z) ≠ x dla wszystkich (u, z) ${\ Displaystyle \ in}$ E (G): z ≠ v .

Wachlarz wierzchołka u to ciąg wierzchołków F[1:k], który spełnia następujące warunki :

F[1:k] jest niepustą sekwencją różnych sąsiadów u
(F [1], u) ${\ Displaystyle \ in}$ E (G) jest bezbarwny
Kolor (F[i+1],u) jest wolny na F[i] dla 1 ≤ i < k

Przykłady ścieżek cd _x : ac,cg,gd to czerwono-zielona ścieżka _{_c} , a bd,dg to czerwono-pomarańczowa ścieżka _{d .}

Biorąc pod uwagę wachlarz F, dowolna krawędź (F[i], X) dla 1 ≤ i ≤ k jest krawędzią wachlarza . Niech c i d będą kolorami. cd _X jest ścieżką krawędzi, która przechodzi przez wierzchołek X, zawiera tylko krawędzie w kolorach c i d i jest maksymalna (nie możemy dodać żadnej innej krawędzi, ponieważ zawierałaby krawędzie o kolorze innym niż {c, d}). Zauważ, że dla wierzchołka X istnieje tylko jedna taka ścieżka, ponieważ co najwyżej jedna krawędź każdego koloru może przylegać do danego wierzchołka.

Obracanie wentylatora

Obracanie wentylatora F = [ x ₁ , x ₂ , x ₃ ] w lewo daje wentylator po prawej stronie

Biorąc pod uwagę wachlarz F [1: k ] wierzchołka X , operacja „obróć wachlarz” wykonuje (równolegle):

c(F[i],X)=c(F[i+1],X)
Usuń kolor (F[k],X)

Ta operacja pozostawia ważne kolorowanie, ponieważ dla każdego i , c ( F [ i + 1], X ) było wolne na ( F [ i ], X ).

Odwracanie ścieżki

Odwrócenie czerwono-zielonej _ścieżki z wykresu po lewej stronie daje wykres po prawej stronie.

Operacja „odwróć ścieżkę cd _X ” zamienia każdą krawędź na ścieżce w kolorze c na d i każdą krawędź w kolorze d na c. Odwrócenie ścieżki może być przydatne do uwolnienia koloru na X, jeśli X jest jednym z punktów końcowych ścieżki: jeśli X sąsiadował z kolorem c, ale nie z d, będzie teraz sąsiadował z kolorem d, a nie c, uwalniając c dla innego krawędź sąsiadująca z X. Operacja odwracania nie zmieni ważności kolorowania, ponieważ dla punktów końcowych tylko jeden z {c, d} może przylegać do wierzchołka, a dla innych elementów ścieżki operacja zmienia tylko kolor krawędzi, żaden nowy kolor nie jest dodawany.

Algorytm

     Algorytm  Algorytm kolorowania krawędzi Misry i Griesa  jest  wprowadzany:  Graf G.  Wynik:  Właściwe kolorowanie c krawędzi G. Niech U := E(G)  podczas gdy  U ≠ ∅  do  Niech (u, v) będzie dowolną krawędzią w U Niech F[1:k] będzie maksymalnym wachlarzem u zaczynając od F[1] = v. Niech c będzie kolorem, który jest wolny na u, a d będzie kolorem, który jest wolny na F[k]. Odwróć płytę CD  _u ścieżka Niech w ∈ V(G) będzie takie, że w ∈ F, F' = [F[1]...w] jest wachlarzem i d jest wolne na w. Obróć F' i ustaw c(u, w) = d.  U := U − {(u, v)}   koniec póki

Dowód poprawności

Poprawność algorytmu została udowodniona w trzech częściach. Najpierw pokazano, że odwrócenie ścieżki cd _u gwarantuje wierzchołek w taki, że w ∈ F , F ' = [ F [1]... w ] jest wachlarzem i d jest wolne na w . Następnie pokazano, że kolorowanie krawędzi jest prawidłowe i wymaga co najwyżej Δ + 1 kolorów.

Gwarancja odwrócenia ścieżki

Przed inwersją istnieją dwa przypadki:

Wachlarz nie ma krawędzi w kolorze d . Ponieważ F jest wachlarzem maksymalnym, a d jest wolny na F [ k ], oznacza to, że nie ma krawędzi o kolorze d sąsiadującej z u , w przeciwnym razie, gdyby istniała, ta krawędź byłaby po F [ k ], ponieważ d jest wolny na F [ k ], ale F było maksymalne, co jest sprzecznością. Zatem d jest wolne na u , a ponieważ c jest również wolny na u , ścieżka cd _u jest pusta, a inwersja nie ma wpływu na wykres. Ustaw w = fa [ k ].
Wachlarz ma jedną krawędź w kolorze d . Niech (u,F[x+1]) będzie tą krawędzią. Zauważ, że x + 1 ≠ 1 ponieważ (u, F[1]) jest bezbarwne. Zatem d jest wolne na F [ x ]. Również x ≠ k , ponieważ wachlarz ma długość k , ale istnieje F [ x + 1]. Możemy teraz pokazać, że po odwróceniu, dla każdego y ∈ {1, ..., x − 1, x + 1, ..., k }, kolor ( F [ y + 1], u ) jest wolny na F[y]. Zauważ, że przed odwróceniem kolor ( u , F [ y + 1]) nie jest c lub d , ponieważ c jest wolny na u i ( u , F [ x + 1]) ma kolor d , a kolorowanie jest ważny. Inwersja dotyczy tylko krawędzi o kolorze c lub d , więc (1) zachodzi.

F [ x ] może znajdować się w ścieżce cd _u lub nie. Jeśli tak nie jest, to inwersja nie wpłynie na zbiór wolnych kolorów na F [ x ], a d pozostanie na nim wolny. Możemy ustawić w = F [ x ]. W przeciwnym razie możemy pokazać, że F jest nadal wachlarzem, a d pozostaje wolny na F [ k ]. Ponieważ d było wolne na F [ x ] przed inwersją i F [ x ] jest na ścieżce, F [ x ] jest punktem końcowym ścieżki cd _u , a c będzie wolne na F [ x ] po odwróceniu. Inwersja zmieni kolor ( u , F [ x + 1]) z d na c . Zatem, ponieważ c jest teraz wolne na F [ x ] i (1) zachodzi, F pozostaje wachlarzem. również, D pozostaje wolny na F [ k ], ponieważ F [ k ] nie leży na ścieżce cd _u (załóżmy, że jest; skoro d jest wolny na F [ k ], to musiałby być końcem ścieżki, ale u a F [ x ] to punkty końcowe). Wybierz w = F [ k ].

W każdym razie wachlarz F ' jest przedrostkiem F , co oznacza, że F ' jest również wachlarzem.

Kolorystyka krawędzi jest prawidłowa

Można to wykazać przez indukcję liczby kolorowych krawędzi. Przypadek podstawowy: żadna krawędź nie jest pokolorowana, jest to prawidłowe. Krok indukcyjny: załóżmy, że tak było na końcu poprzedniej iteracji. W obecnej iteracji, po odwróceniu ścieżki, d będzie wolne na u , a według poprzedniego wyniku będzie również wolne na w . Obracanie F ' nie wpływa na ważność zabarwienia. Zatem po ustawieniu c ( u , w ) = d kolorowanie jest nadal aktualne.

Algorytm wymaga co najwyżej Δ + 1 kolorów

W danym kroku używane są tylko kolory c i d . Ponieważ u sąsiaduje z co najmniej jedną niekolorową krawędzią, a jej stopień jest ograniczony przez Δ, co najmniej jeden kolor w {1,...,Δ} jest dostępny dla c . Dla d , F [ k ] może mieć stopień Δ i nie mieć niebarwionej sąsiedniej krawędzi. W związku z tym może być wymagany kolor Δ + 1.

Złożoność

W każdym kroku obrót odbarwia krawędź (u,w), jednocześnie kolorując krawędzie (u,F[1]) i (u,v), które wcześniej były odbarwione. W ten sposób jedna dodatkowa krawędź zostaje pokolorowana. $W$ pętla . $Znalezienie maksymalnego$ d oraz odwrócenie ścieżki cd _u można w Znalezienie w i obrócenie F' zajmuje ${\ Displaystyle O (\ stopień (u)) \ w O (| V |)}$ czas. Znalezienie i $czasie$ w stałym czasie (wyjmij ostatni element), a ten stos . $iteracja$ pętli zajmuje a całkowity ${\ Displaystyle O (| E | + | E | | V |) = O (| E | | V |)}$ .