Kolorowanie wykresu - Graph coloring

Prawidłowe pokolorowanie wierzchołków wykresu Petersena za pomocą 3 kolorów, minimalna możliwa liczba.

W teorii wykres , wykres barwiących jest szczególnym przypadkiem etykietowania wykresu ; jest to przypisanie etykiet tradycyjnie nazywanych „kolorami” do elementów grafu podlegających pewnym ograniczeniom. W najprostszej formie jest to sposób na kolorowanie wierzchołków grafu w taki sposób, że żadne dwa sąsiadujące ze sobą wierzchołki nie są tego samego koloru; nazywa się to kolorowaniem wierzchołków . Podobnie, kolorowanie krawędzi przypisuje kolor do każdej krawędzi, tak że żadne dwie sąsiednie krawędzie nie są tego samego koloru, a kolorowanie powierzchni wykresu planarnego przypisuje kolor do każdej ściany lub regionu, aby żadne dwie ściany, które dzielą granicę, nie miały taki sam kolor.

Kolorowanie wierzchołków jest zwykle używane do wprowadzenia problemów z kolorowaniem grafów, ponieważ inne problemy z kolorowaniem można przekształcić w instancję kolorowania wierzchołków. Na przykład, kolorowanie krawędzi grafu jest tylko kolorowaniem wierzchołków jego wykresu liniowego , a kolorowanie twarzy grafu płaskiego jest tylko kolorowaniem wierzchołków jego podwójnego . Jednak problemy z barwieniem niezwiązanym z wierzchołkami są często określane i badane bez zmian. Jest to częściowo pedagogiczne , a częściowo dlatego, że niektóre problemy najlepiej badać w formie niewierzchołkowej, jak w przypadku kolorowania krawędzi.

Konwencja używania kolorów wywodzi się z kolorowania krajów na mapie , gdzie każda twarz jest dosłownie pokolorowana. Zostało to uogólnione na kolorowanie powierzchni wykresu osadzonego w płaszczyźnie. Przez dualność planarną stał się kolorowaniem wierzchołków iw tej postaci uogólnia na wszystkie grafy. W reprezentacjach matematycznych i komputerowych typowo używa się pierwszych kilku dodatnich lub nieujemnych liczb całkowitych jako „kolorów”. Generalnie, jako „zestaw kolorów” można użyć dowolnego skończonego zbioru . Charakter problemu z kolorowaniem zależy od liczby kolorów, ale nie od tego, czym one są.

Kolorowanie grafów cieszy się wieloma praktycznymi zastosowaniami, jak również wyzwaniami teoretycznymi. Oprócz klasycznych typów problemów, różne ograniczenia mogą być również ustawione na wykresie, w sposobie przypisywania koloru, a nawet na samym kolorze. Osiągnął nawet popularność wśród ogółu społeczeństwa w postaci popularnej układanki liczbowej Sudoku . Kolorowanie wykresów jest nadal bardzo aktywną dziedziną badań.

Uwaga: Wiele terminów użytych w tym artykule jest zdefiniowanych w Słowniku teorii grafów .

Historia

Pierwsze wyniki dotyczące kolorowania grafów dotyczą prawie wyłącznie grafów planarnych w postaci kolorowania map . Próbując pokolorować mapę hrabstw Anglii, Francis Guthrie postulował hipotezę czterech kolorów , zauważając, że cztery kolory były wystarczające do pokolorowania mapy, aby żaden region o wspólnej granicy nie otrzymał tego samego koloru. Brat Guthrie przekazał to pytanie swojemu nauczycielowi matematyki Augustusowi de Morganowi z University College , który wspomniał o nim w liście do Williama Hamiltona w 1852 roku. Arthur Cayley poruszył ten problem na spotkaniu London Mathematical Society w 1879 roku. W tym samym roku Alfred Kempe opublikował artykuł, w którym twierdził, że udało się ustalić wynik, i przez dekadę uważano, że problem czterech kolorów został rozwiązany. Za swoje osiągnięcie Kempe został wybrany członkiem Towarzystwa Królewskiego, a później prezesem London Mathematical Society.

W 1890 Heawood zauważył, że argument Kempe był błędny. Jednak w tym artykule udowodnił twierdzenie o pięciu kolorach , mówiąc, że każda mapa planarna może być pokolorowana nie więcej niż pięcioma kolorami, korzystając z idei Kempe. W następnym stuleciu opracowano ogromną ilość pracy i teorii mających na celu zmniejszenie liczby kolorów do czterech, aż do ostatecznego udowodnienia twierdzenia o czterech kolorach w 1976 roku przez Kennetha Appela i Wolfganga Hakena . Dowód powrócił do pomysłów Heawooda i Kempe iw dużej mierze zignorował rozwój wydarzeń. Dowód twierdzenia o czterech kolorach jest również godny uwagi, ponieważ jest pierwszym ważnym dowodem wspomaganym komputerowo.

W 1912 roku George David Birkhoff wprowadził chromatyczną wielomian studiowania kolorystyka problemy, które zostało uogólnione do wielomianu tutte przez tutte , ważnych struktur algebraicznych teorii grafów . Kempe zwrócił uwagę na ogólny, nieplanarny przypadek już w 1879 roku, a na początku XX wieku pojawiło się wiele wyników dotyczących uogólnień kolorowania grafów planarnych na powierzchnie wyższego rzędu.

W 1960 r. Claude Berge sformułował inną hipotezę dotyczącą kolorowania grafu, hipotezę silnego doskonałego grafu , pierwotnie motywowaną koncepcją teorii informacji, zwaną zdolnością zerowego błędu grafu, wprowadzoną przez Shannona . Przypuszczenie pozostawało nierozwiązane przez 40 lat, dopóki nie zostało ustalone jako słynne twierdzenie o silnym grafie doskonałym przez Chudnovsky'ego , Robertsona , Seymoura i Thomasa w 2002 roku.

Kolorowanie grafów było badane jako problem algorytmiczny od wczesnych lat 70. XX wieku: problem liczby chromatycznej (patrz poniżej ) jest jednym z 21 problemów NP-zupełnych Karpa z 1972 r. i mniej więcej w tym samym czasie opracowano różne algorytmy czasu wykładniczego oparte na nawracaniu. oraz o nawrocie delecji-skurczu Zykowa (1949) . Jedno z głównych zastosowań kolorowania grafów, alokacja rejestrów w kompilatorach, zostało wprowadzone w 1981 roku.

Definicja i terminologia

Ten wykres może mieć trzy kolory na 12 różnych sposobów.

Kolorowanie wierzchołków

W przypadku użycia bez żadnych zastrzeżeń, kolorowanie grafu jest prawie zawsze właściwym kolorowaniem wierzchołków , a mianowicie oznaczanie wierzchołków grafu kolorami tak, że żadne dwa wierzchołki o tej samej krawędzi nie mają tego samego koloru. Ponieważ wierzchołek z pętlą (tj. połączeniem bezpośrednio z samym sobą) nigdy nie mógłby być odpowiednio pokolorowany, zrozumiałe jest, że grafy w tym kontekście są bezpętlowe.

Terminologia używania kolorów dla etykiet wierzchołków sięga do kolorowania mapy. Etykiety takie jak czerwony i niebieski są używane tylko wtedy, gdy liczba kolorów jest niewielka i zwykle rozumie się, że etykiety są rysowane z liczb całkowitych {1, 2, 3, ...}.

Kolorowanie przy użyciu co najwyżej k kolorów nazywa się (właściwym) k -kolorowaniem . Najmniejsza liczba kolorów potrzebna do pokolorowania wykresu G nazywana jest jego liczbą chromatyczną i często oznaczana jest jako χ( G ). Czasami używa się γ( G ), ponieważ χ( G ) jest również używane do oznaczenia charakterystyki Eulera grafu. Wykres, któremu można przypisać (właściwe) k -kolorowanie, jest k -kolorowalny i jest k -chromatyczny, jeśli jego liczba chromatyczna wynosi dokładnie k . Podzbiór wierzchołków przypisanych do tego samego koloru nazywany jest klasą koloru , każda taka klasa tworzy niezależny zestaw . Zatem k- kolorowanie jest tym samym, co podział zbioru wierzchołków na k niezależnych zbiorów, a terminy k-częściowe i k-kolorowalne mają to samo znaczenie.

Wielomian chromatyczny

Wszystkie nieizomorficzne grafy na 3 wierzchołkach i ich wielomiany chromatyczne. Pusty wykres E ₃ (czerwony) dopuszcza 1-kolorowanie; inni przyznają

W chromatyczne wielomianowe zlicza ilość sposobów wykres mogą być barwione przy użyciu niektórych z danej liczby kolorów. Na przykład, używając trzech kolorów, wykres na sąsiednim obrazie można pokolorować na 12 sposobów. Mając tylko dwa kolory, w ogóle nie można go pokolorować. Dzięki czterem kolorom można go pokolorować na 24 + 4⋅12 = 72 sposoby: używając wszystkich czterech kolorów, są 4! = 24 poprawne kolorowania ( każde przypisanie czterech kolorów do dowolnego wykresu 4-wierzchołkowego jest prawidłowym kolorowaniem); a dla każdego wyboru trzech z czterech kolorów jest 12 ważnych trzech kolorów. Tak więc dla wykresu w przykładzie tabela z liczbą prawidłowych kolorowań zaczynałaby się tak:

Wielomian chromatyczny to funkcja, która zlicza liczbę t -kolorowań . Jak sama nazwa wskazuje, dla danej funkcji jest rzeczywiście wielomianem w . Dla przykładowego wykresu , i rzeczywiście . ${\ Displaystyle P (G, t)}$${\ Displaystyle G}$${\ Displaystyle G}$${\displaystyle t}$${\ Displaystyle P (G, t) = t (t-1) ^ {2} (t-2)}$${\ Displaystyle P (G, 4) = 72}$

Wielomian chromatyczny zawiera więcej informacji o zabarwieniu G niż liczba chromatyczna. Rzeczywiście, χ jest najmniejszą dodatnią liczbą całkowitą, która nie jest zerem wielomianu chromatycznego:

${\ Displaystyle \ chi (G) = \ min \ {k \, \ dwukropek \, P (G, k)> 0 \}.}$

Wielomiany chromatyczne dla niektórych grafów

Trójkąt K 3	${\ Displaystyle t (t-1) (t-2)}$
Kompletny wykres K n	${\ Displaystyle t (t-1) (t-2) \ cdots (t-(n-1))}$
Drzewo o n wierzchołkach	${\ Displaystyle t (t-1) ^ {n-1}}$
Cykl C n	${\ Displaystyle (t-1) ^ {n} + (-1) ^ {n} (t-1)}$
Wykres Petersena	${\ Displaystyle t (t-1) (t-2) (t ^ {7} -12 t ^ {6} + 67 t ^ {5} -230 t ^ {4} + 529 t ^ {3}-814 t ^ {2} +775t-352)}$

Kolorowanie krawędzi

Kolorowanie krawędzi wykresu jest odpowiedni zabarwienie krawędzi , to znaczy zadanie kolorów do krawędzi, tak aby nie wierzchołek pada dwóch krawędzi tego samego koloru. Kolorowanie krawędzi za pomocą k kolorów nazywa się k -kolorowaniem krawędzi i jest równoważne z problemem podziału zestawu krawędzi na k dopasowań . Najmniejsza liczba kolorów, potrzebne do barwienia krawędzi grafu G jest wskaźnik chromatyczne albo krawędź liczba chromatycznej , χ '( G ). Tait barwiących jest farbowanie 3-krawędź sześcienny wykresie . Twierdzenie o czterech kolorach jest równoważne twierdzeniu, że każdy płaski sześcienny graf bez mostków dopuszcza kolorowanie Tait.

Całkowite zabarwienie

Kolorowanie całkowite to rodzaj kolorowania wierzchołków i krawędzi grafu. W przypadku użycia bez żadnych zastrzeżeń, całkowite kolorowanie jest zawsze zakładane jako właściwe w tym sensie, że żadnemu sąsiadującemu wierzchołkowi, żadnej sąsiadującej krawędzi ani żadnej krawędzi i jej wierzchołkom końcowym nie przypisano tego samego koloru. Całkowita liczba chromatyczna χ″ ( G ) wykresu G to najmniejsza liczba kolorów potrzebna w każdym całkowitym zabarwieniu G.

Nieoznakowane kolorystyka

Nieznakowanego barwiących wykresu jest orbity barwiących pod działaniem grupy automorfizm wykresu. Zwróć uwagę, że kolory pozostają oznaczone; jest to wykres, który nie ma etykiety. Istnieje odpowiednik wielomianu chromatycznego, który zlicza liczbę nieoznaczonych zabarwień wykresu z danego skończonego zestawu kolorów.

Jeśli zinterpretujemy kolorowanie grafu na wierzchołkach jako wektor w , działaniem automorfizmu jest permutacja współczynników w wektorze kolorowania. ${\displaystyle d}$${\ Displaystyle \ mathbb {Z} ^ {d}}$

Nieruchomości

Górne granice liczby chromatycznej

Przypisanie odrębnych kolorów do różnych wierzchołków zawsze daje właściwe zabarwienie, więc

${\ Displaystyle 1 \ leq \ chi (G) \ leq n.}$

Jedyne wykresy, które mogą być jednokolorowe, to wykresy bez krawędzi . Zakończeniu wykres z n wierzchołków wymaga kolorów. W optymalnym kolorowaniu musi być co najmniej jedna z m krawędzi grafu pomiędzy każdą parą klas kolorów, więc ${\ Displaystyle K_ {n}}$${\ Displaystyle \ chi (K_ {n}) = n}$

${\ Displaystyle \ chi (G) (\ chi (G)-1) \ równoważnik 2 m.}$

Jeśli G zawiera klikę o rozmiarze k , to do pokolorowania tej kliki potrzeba co najmniej k kolorów; innymi słowy, liczba chromatyczna jest co najmniej liczbą kliki:

${\ Displaystyle \ chi (G) \ geq \ omega (G).}$

Dla doskonałych wykresów to ograniczenie jest ciasne. Znajdowanie klik jest znane jako problem kliki .

Bardziej ogólnie rodzina wykresów jest -bounded jeśli jest jakaś funkcja taka, że wykresy w można barwić w większości kolorów, dla rodziny doskonałych wykresów to funkcja jest . ${\displaystyle {\mathcal {F}}}$${\ Displaystyle \ chi}$${\displaystyle c}$${\ Displaystyle G}$${\displaystyle {\mathcal {F}}}$${\displaystyle c(\omega (G))}$${\ Displaystyle c (\ omega (G)) = \ omega (G)}$

Dwukolorowe wykresy to dokładnie wykresy dwudzielne , obejmujące drzewa i lasy. Zgodnie z twierdzeniem o czterech kolorach, każdy graf planarny może być czterokolorowy.

A chciwi barwiące pokazuje, że każdy wykres może być barwiona jednym kolorem więcej niż maksimum wierzchołka stopnia ,

${\ Displaystyle \ chi (G) \ leq \ Delta (G) + 1.}$

Pełne wykresy mają i , a nieparzyste cykle mają i , więc dla tych wykresów to ograniczenie jest najlepsze z możliwych. We wszystkich innych przypadkach wiązanie można nieco poprawić; Twierdzenie Brooksa mówi, że ${\ Displaystyle \ chi (G) = n}$${\ Displaystyle \ Delta (G) = n-1}$${\ Displaystyle \ chi (G) = 3}$${\ Displaystyle \ Delta (G) = 2}$

Twierdzenie Brooksa : dla połączonego, prostego grafu G , chyba że G jest grafem pełnym lub nieparzystym cyklem.${\ Displaystyle \ chi (G) \ leq \ Delta (G)}$

Dolne granice liczby chromatycznej

Na przestrzeni lat odkryto kilka dolnych granic dla granic chromatycznych:

Wiązanie Hoffmana: Niech będzie rzeczywistą macierzą symetryczną taką, że kiedykolwiek nie jest krawędzią w . Zdefiniuj , gdzie są największe i najmniejsze wartości własne . Zdefiniuj , jak powyżej. Następnie: ${\ Displaystyle W}$${\ Displaystyle W_ {i, j} = 0}$${\ Displaystyle (i, j)}$${\ Displaystyle G}$${\ Displaystyle \ chi _ {W} (G) = 1 - {\ tfrac {\ lambda _ {\ max} (W)} {\ lambda _ {\ min} (W)}}}$${\ Displaystyle \ lambda _ {\ max} (W), \ lambda _ {\ min} (W)}$${\ Displaystyle W}$${\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$${\ Displaystyle W}$

${\ Displaystyle \ chi _ {H} (G) \ leq \ chi (G).}$

Wektorowa liczba chromatyczna :Niechbędzie dodatnią półokreśloną macierzą taką, żekiedykolwiekjest krawędzią w. Zdefiniujjako najmniejsze k, dla którychistnieje takamacierz. Następnie ${\ Displaystyle W}$${\ Displaystyle W_ {i, j} \ leq - {\ tfrac {1} {k-1}}}$${\ Displaystyle (i, j)}$${\ Displaystyle G}$${\ Displaystyle \ chi _ {V} (G)}$${\ Displaystyle W}$

${\ Displaystyle \ chi _ {V} (G) \ leq \ chi (G).}$

Liczba Lovásza : Liczba Lovásza grafu komplementarnego jest również dolnym ograniczeniem liczby chromatycznej:

${\ Displaystyle \ vartheta ({\ bar {G}}) \ leq \ chi (G).}$

Ułamkowa liczba chromatyczna : Ułamkowa liczba chromatyczna wykresu jest również dolną granicą liczby chromatycznej:

${\ Displaystyle \ chi _ {f} (G) \ leq \ chi (G).}$

Te granice są uporządkowane w następujący sposób:

${\ Displaystyle \ chi _ {H} (G) \ leq \ chi _ {V} (G) \ leq \ vartheta ({\ bar {G}}) \ leq \ chi _ {f} (G) \ leq \ chi (G).}$

Wykresy o wysokiej liczbie chromatycznej

Wykresy z dużymi klikami mają wysoką liczbę chromatyczną, ale nie jest odwrotnie. Wykres Grötzsch jest przykładem 4-chromatycznej wykres bez trójkąta, a przykładem może być uogólnione do Mycielskians .

Twierdzenie ( William T. Tutte  1947 , Alexander Zykov  1949 , Jan Mycielski  1955 ): Istnieją grafy bez trójkątów z dowolnie wysoką liczbą chromatyczną.

Aby to udowodnić, zarówno Mycielski, jak i Zykov podali konstrukcję indukcyjnie zdefiniowanej rodziny grafów bez trójkątów, ale z dowolnie dużą liczbą chromatyczną. Burling (1965) skonstruował pudełka wyrównane do osi, w których wykres przecięcia jest wolny od trójkątów i wymaga arbitralnie wielu kolorów, aby były odpowiednio pokolorowane. Ta rodzina grafów nazywana jest wówczas grafami Burlinga. Ta sama klasa grafów jest używana do budowy rodziny odcinków linii bez trójkątów w płaszczyźnie, podanej przez Pawlika i in. glin. (2014). Pokazuje, że liczba chromatyczna jego wykresu przecięcia jest również dowolnie duża. Oznacza to zatem, że pola wyrównane do osi w oraz segmenty linii w nie są ograniczone . ${\ Displaystyle \ mathbb {R} ^ {3}}$${\ Displaystyle \ mathbb {R} ^ {3}}$${\ Displaystyle \ mathbb {R} ^ {2}}$

Z twierdzenia Brooksa grafy o dużej liczbie chromatycznej muszą mieć wysoki stopień maksymalny. Jednak podatność na kolorowanie nie jest zjawiskiem całkowicie lokalnym: wykres o dużym obwodzie wygląda lokalnie jak drzewo, ponieważ wszystkie cykle są długie, ale jego liczba chromatyczna nie musi wynosić 2:

Twierdzenie ( Erdős ): Istnieją wykresy o dowolnie dużym obwodzie i liczbie chromatycznej.

Granice na indeksie chromatycznym

Kolorowanie krawędzi G jest kolorowaniem wierzchołków jego wykresu liniowego i na odwrót. Zatem, ${\ Displaystyle L(G)}$

${\ Displaystyle \ chi '(G) = \ chi (L (G)).}$

Istnieje silny związek między kolorowalnością krawędzi a maksymalnym stopniem wykresu . Ponieważ wszystkie krawędzie przychodzące do tego samego wierzchołka wymagają własnego koloru, mamy ${\ Displaystyle \ Delta (G)}$

${\ Displaystyle \ chi '(G) \ geq \ Delta (G).}$

Ponadto,

Twierdzenie Kőniga : jeśli G jest dwudzielne.${\ Displaystyle \ chi '(G) = \ Delta (G)}$

Ogólnie rzecz biorąc, związek jest nawet silniejszy niż twierdzenie Brooksa dotyczące kolorowania wierzchołków:

Twierdzenie Viizinga: Wykres maksymalnego stopniama liczbę krawędziowo-chromatycznąlub.${\ Displaystyle \ Delta}$${\ Displaystyle \ Delta}$${\ Displaystyle \ Delta +1}$

Inne właściwości

Wykres ma k -kolorowanie wtedy i tylko wtedy, gdy ma orientację acykliczną, dla której najdłuższa ścieżka ma długość co najwyżej k ; jest to twierdzenie Gallai-Hasse-Roya-Vitavera ( Nešetřil i Ossona de Mendez 2012 ).

W przypadku grafów planarnych kolorowanie wierzchołków jest zasadniczo dualne do przepływów nigdzie-zero .

O nieskończonych wykresach wiadomo znacznie mniej. Poniżej znajdują się dwa z kilku wyników dotyczących nieskończonego kolorowania wykresu:

• Jeśli wszystkie skończone podgrafy nieskończonego grafu G są k- kolorowalne, to tak samo jest z G , przy założeniu aksjomatu wyboru . To de Bruijn-Erdősa Twierdzenie o de Bruijn i Erdös (1951) .
• Jeśli graf dopuszcza pełne n- kolorowanie dla każdego n ≥ n ₀ , to dopuszcza nieskończone pełne kolorowanie ( Fawcett 1978 ).

Otwarte problemy

Jak stwierdzono powyżej, przypuszczenie Reeda z 1998 roku jest takie, że wartość jest zasadniczo bliższa dolnej granicy, ${\ Displaystyle \ omega (G) \ równoważnik \ chi (G) \ równoważnik \ Delta (G) + 1.}$${\ Displaystyle \ chi (G) \ leq \ lewo \ lceil {\ Frac {\ omega (G) + \ Delta (G) + 1} {2}} \ po prawej \ rceil.}$

Liczba chromatyczna płaszczyzny , gdzie dwa punkty sąsiadują ze sobą, jeśli mają jednostkę odległości, jest nieznana, chociaż jest to jedna z 5, 6 lub 7. Inne otwarte problemy dotyczące liczby chromatycznej grafów obejmują przypuszczenie Hadwigera , że każdy graf o liczbie chromatycznej k ma kompletny wykres na k wierzchołków jako a minor , hipoteza Erdősa-Fabera-Lovásza ograniczająca liczbę chromatyczną sum pełnych grafów, które mają co najwyżej jeden wspólny wierzchołek dla każdej pary, oraz hipoteza Albertsona, że wśród k grafy -chromatyczne pełne grafy to grafy o najmniejszej liczbie przecięcia .

Kiedy Birkhoff i Lewis wprowadzili wielomian chromatyczny w swoim ataku na twierdzenie o czterech kolorach, wywnioskowali, że w przypadku grafów płaskich G wielomian nie ma zer w regionie . Chociaż wiadomo, że taki wielomian chromatyczny nie ma zer w regionie, a ich przypuszczenie jest nadal nierozstrzygnięte. Nierozwiązanym problemem pozostaje również scharakteryzowanie grafów, które mają ten sam wielomian chromatyczny i określenie, które wielomiany są chromatyczne. ${\ Displaystyle P (G, t)}$${\displaystyle [4,\infty )}$${\displaystyle [5,\infty )}$${\ Displaystyle P (G, 4) \ neq 0}$

Algorytmy

Kolorowanie wykresu
Decyzja
Nazwa	Kolorowanie wykresu, kolorowanie wierzchołków, k -kolorowanie
Wejście	Wykres G z n wierzchołkami. Liczba całkowita k
Wyjście	Czy G dopuszcza prawidłowe kolorowanie wierzchołków za pomocą k kolorów?
Czas trwania	O(2 n n )
Złożoność	NP-zupełna
Redukcja z	3-Satysfakcja
Garey-Johnson	GT4
Optymalizacja
Nazwa	Liczba chromatyczna
Wejście	Wykres G z n wierzchołkami.
Wyjście	( G )
Złożoność	NP-twarde
Przybliżalność	O( n  (log n ) -3 (log log n ) 2 )
Niezbliżalność	O( n 1−ε ) chyba że P = NP
Problem z liczeniem
Nazwa	Wielomian chromatyczny
Wejście	Wykres G z n wierzchołkami. Liczba całkowita k
Wyjście	Liczba P  ( G , k ) właściwych k -podbarwień G
Czas trwania	O(2 n n )
Złożoność	#P-kompletne
Przybliżalność	FPRAS dla ograniczonych przypadków
Niezbliżalność	Brak PTAS, chyba że P = NP

Czas wielomianowy

Ustalenie, czy wykres może być pokolorowany dwoma kolorami, jest równoważne określeniu, czy wykres jest dwuczęściowy , a zatem obliczalny w czasie liniowym przy użyciu przeszukiwania wszerz lub przeszukiwania w głąb . Mówiąc bardziej ogólnie, liczba chromatyczna i odpowiadające jej kolorowanie doskonałych wykresów można obliczyć w czasie wielomianowym przy użyciu programowania półokreślonego . Zamknięte formuły wielomianu chromatycznego są znane dla wielu klas grafów, takich jak lasy, grafy akordowe, cykle, koła i drabiny, dzięki czemu można je oceniać w czasie wielomianowym.

Jeśli wykres jest planarny i ma małą szerokość gałęzi (lub jest nieplanarny, ale ze znanym rozkładem gałęzi), to można go rozwiązać w czasie wielomianowym za pomocą programowania dynamicznego. Ogólnie wymagany czas jest wielomianem w rozmiarze wykresu, ale wykładniczym w szerokości gałęzi.

Dokładne algorytmy

Wyszukiwanie brutalne dla k -kolorowania bierze pod uwagę każde przypisanie k kolorów do n wierzchołków i sprawdza dla każdego, czy jest to prawidłowe. Aby obliczyć liczbę chromatyczną i wielomian chromatyczny, ta procedura jest używana dla każdego , niepraktyczne dla wszystkich, z wyjątkiem najmniejszych wykresów wejściowych. ${\ Displaystyle k ^ {n}}$${\displaystyle k=1,\ldots,n-1}$

Używając programowania dynamicznego i ograniczenia liczby maksymalnych niezależnych zbiorów , k- kolorowalność można określić w czasie i przestrzeni . Stosując zasadę inkluzji-wykluczenia i algorytm Yatesa dla szybkiej transformacji zeta, k- kolorowalność można określić w czasie dla dowolnego k . Szybsze algorytmy są znane z 3- i 4-kolorowalności, o których można zdecydować odpowiednio w czasie i . ${\ Displaystyle O (2,4423 ^ {n})}$${\ Displaystyle O (2 ^ {n} n)}$${\ Displaystyle O (1,3289 ^ {n})}$${\ Displaystyle O (1,7272 ^ {n})}$

Skurcz

Skurcz grafu G jest wykresem uzyskać przez określenie wierzchołków U i V , i usunięcie krawędzie pomiędzy nimi. Pozostałe krawędzie pierwotnie związane z u lub v są teraz przypadkowe przy ich identyfikacji. Operacja ta odgrywa ważną rolę w analizie kolorowania grafów. ${\displaystyle G/uv}$

Liczba chromatyczna spełnia relację rekurencyjną :

${\ Displaystyle \ chi (G) = {\ tekst {min}} \ {\ chi (G + uv), \ chi (G / uv) \}}$

ze względu na Zykov (1949) , gdzie u i v są niesąsiadującymi wierzchołkami i jest grafem z dodaną krawędzią uv . Kilka algorytmów opiera się na ocenie tej powtarzalności, a wynikowe drzewo obliczeniowe jest czasami nazywane drzewem Zykova. Czas działania jest oparty na heurystyce wyboru wierzchołków u i v . ${\displaystyle G+uv}$

Wielomian chromatyczny spełnia następującą relację rekurencyjną

${\ Displaystyle P (G-uv, k) = P (G/uv, k) + P (G, k)}$

gdzie u i v są sąsiednimi wierzchołkami i jest wykresem z usuniętą krawędzią uv . reprezentuje liczbę możliwych prawidłowych kolorowań wykresu, gdzie wierzchołki mogą mieć te same lub różne kolory. Wtedy właściwe zabarwienia powstają z dwóch różnych wykresów. Aby wyjaśnić, jeśli wierzchołki u i v mają różne kolory, możemy równie dobrze rozważyć wykres, w którym u i v sąsiadują ze sobą. Jeśli u i v mają te same kolory, równie dobrze moglibyśmy rozważyć wykres, w którym u i v są skrócone. Tutte ciekawość „s, o której inne właściwości wykresu usatysfakcjonowany Nawrót doprowadziły go do odkrycia uogólnienie dwuwymiarowych chromatycznej wielomianu, z wielomianem tutte . ${\ Displaystyle G-uv}$${\ Displaystyle P (G-uv, k)}$

Wyrażenia te dają początek rekurencyjnej procedurze zwanej algorytmem skrócenia-skreślenia , która stanowi podstawę wielu algorytmów kolorowania grafów. Czas działania spełnia tę samą relację powtarzalności co liczby Fibonacciego , więc w najgorszym przypadku algorytm działa w czasie w ramach współczynnika wielomianu dla n wierzchołków i m krawędzi. Analiza może być poprawiona w granicach wielomianu współczynnik liczby z drzew rozpinających grafu wejściowego. W praktyce, aby uniknąć niektórych wywołań rekurencyjnych, stosuje się strategie rozgałęzione i ograniczone oraz odrzucanie izomorfizmu grafu . Czas działania zależy od heurystyki użytej do wybrania pary wierzchołków. ${\ Displaystyle \ lewo ({\ tfrac {1 + {\ sqrt {5}}} {2}} \ prawej) ^ {n + m} = O (1,6180 ^ {n + m})}$${\ Displaystyle t (G)}$

Chciwy kolorowanie

Dwa zachłanne kolorowania tego samego wykresu przy użyciu różnych porządków wierzchołków. Prawy przykład uogólnia na wykresy dwukolorowe z n wierzchołkami, gdzie zachłanny algorytm rozszerza kolory.${\displaystyle n/2}$

Algorytm zachłanny uważa wierzchołki w kolejności określonej , ..., i przypisuje najmniejszego dostępnego koloru nie używane przez „s wśród sąsiadów , ..., dodając świeży kolor, jeśli potrzebne. Jakość powstałej kolorystyki zależy od wybranej kolejności. Istnieje kolejność, która prowadzi do zachłannego kolorowania z optymalną ilością kolorów. Z drugiej strony chciwe kolory mogą być arbitralnie złe; na przykład wykres korony na n wierzchołkach może być dwukolorowy, ale ma kolejność, która prowadzi do zachłannego kolorowania kolorami. ${\displaystyle v_{1}}$${\displaystyle v_{n}}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle v_{1}}$${\ Displaystyle v_ {i-1}}$${\ Displaystyle \ chi (G)}$${\displaystyle n/2}$

W przypadku grafów akordowych oraz w szczególnych przypadkach grafów akordowych, takich jak grafy interwałowe i grafy obojętności , algorytm zachłannego kolorowania może być użyty do znalezienia optymalnych kolorowań w czasie wielomianowym, wybierając porządek wierzchołków jako odwrotność porządku eliminacji doskonałej dla wykres. Te doskonale zamawiane wykresy uogólnić tę właściwość, ale jest NP-trudne do znalezienia doskonałego uporządkowania tych wykresów.

Jeśli wierzchołki są uporządkowane według ich stopni , wynikowe kolorowanie zachłanne wykorzystuje co najwyżej kolory, co najwyżej jeden stopień więcej niż maksymalny stopień wykresu. Ta heurystyka jest czasami nazywana algorytmem Welsh-Powell. Kolejna heurystyka spowodowana przez Brélaza ustala kolejność dynamicznie w trakcie działania algorytmu, wybierając następnie wierzchołek sąsiadujący z największą liczbą różnych kolorów. Wiele innych heurystyk kolorowania grafów jest podobnie opartych na zachłannym kolorowaniu dla określonej statycznej lub dynamicznej strategii porządkowania wierzchołków; algorytmy te są czasami nazywane algorytmami kolorowania sekwencyjnego . ${\ Displaystyle {\ tekst {max}} _ {i} {\ tekst {min}} \ {d (x_ {i}) + 1, ja \}}$

Maksymalna (najgorsza) liczba kolorów, jaką można uzyskać za pomocą algorytmu zachłannego, przy użyciu kolejności wierzchołków wybranej w celu maksymalizacji tej liczby, nazywa się liczbą Grundy'ego grafu.

Algorytmy równoległe i rozproszone

W dziedzinie algorytmów rozproszonych kolorowanie grafów jest ściśle związane z problemem łamania symetrii . Obecne najnowocześniejsze algorytmy randomizowane są szybsze dla wystarczająco dużego maksymalnego stopnia Δ niż algorytmy deterministyczne. Najszybsze algorytmy randomizowane wykorzystują technikę wielu prób Schneidera i in.

W symetryczny wykres , A deterministyczny algorytm rozdzielane nie może znaleźć odpowiednie kolorowanie wierzchołek. Aby złamać symetrię, potrzebne są pewne informacje pomocnicze. Standardowym założeniem jest, że początkowo każdy węzeł ma unikalny identyfikator , np. ze zbioru {1, 2, ..., n }. Inaczej mówiąc, zakładamy, że dane nam jest n -kolorowanie. Wyzwaniem jest zmniejszenie liczby kolorów z n do np. Δ + 1. Im więcej kolorów jest użytych, np. O(Δ) zamiast Δ + 1, tym mniej rund komunikacyjnych jest wymaganych.

Prosta, rozproszona wersja algorytmu zachłannego kolorowania (Δ + 1) wymaga Θ ( n ) rund komunikacyjnych w najgorszym przypadku — informacja może wymagać propagowania z jednej strony sieci na drugą.

Najprostszym interesującym przypadkiem jest n - cykl . Richard Cole i Uzi Vishkin pokazują, że istnieje algorytm rozproszony, który redukuje liczbę kolorów z n do O (log  n ) w jednym kroku komunikacji synchronicznej. Poprzez iterację tej samej procedury możliwe jest otrzymanie 3-kolorowania n- cyklu w O ( log *  n ) krokach komunikacji (przy założeniu, że posiadamy unikalne identyfikatory węzłów).

Funkcja log * , iterowany logarytm , jest niezwykle wolno rosnącą funkcją, "prawie stałą". Stąd wynik Cole'a i Vishkina postawił pytanie, czy istnieje algorytm o rozkładzie czasu stałego dla 3-kolorowania n- cyklu. Linial (1992) pokazał, że nie jest to możliwe: każdy deterministyczny algorytm rozproszony wymaga Ω( log *  n ) kroków komunikacyjnych, aby zredukować n -kolorowanie do 3-kolorowania w n- cyklu.

Technika Cole'a i Vishkina może być również zastosowana w dowolnych grafach o ograniczonym stopniu; czas działania to poli(Δ) + O ( log *  n ). Technika została rozszerzona na grafy dysków jednostkowych przez Schneidera i in. Najszybsze algorytmy deterministyczne dla kolorowania (Δ + 1) dla małego Δ są dziełem Leonida Barenboima, Michaela Elkina i Fabiana Kuhna. Algorytm Barenboima i in. działa w czasie O (Δ) +  log * ( n )/2, który jest optymalny pod względem n, ponieważ stały współczynnik 1/2 nie może być poprawiony ze względu na dolną granicę Linial. Panconesi i Srinivasan (1996) używają dekompozycji sieci do obliczenia kolorowania Δ+1 w czasie . ${\ Displaystyle 2 ^ {O \ lewo ({\ sqrt {\ log n}} \ po prawej)}}$

W modelu rozproszonym zbadano również problem kolorowania krawędzi. Panconesi i Rizzi (2001) osiągają w tym modelu kolorowanie (2Δ − 1) w czasie O (Δ +  log *  n ). Dolna granica dla rozłożonego kolorowania wierzchołków z powodu Liniala (1992) dotyczy również problemu rozłożonego kolorowania krawędzi.

Zdecentralizowane algorytmy

Algorytmy zdecentralizowane to takie, w których nie jest dozwolone przekazywanie wiadomości (w przeciwieństwie do algorytmów rozproszonych, w których ma miejsce lokalne przekazywanie wiadomości) i istnieją wydajne algorytmy zdecentralizowane, które będą kolorować wykres, jeśli istnieje odpowiedni kolor. Zakłada się, że wierzchołek jest w stanie wykryć, czy którykolwiek z jego sąsiadów używa tego samego koloru co wierzchołek, tj. czy istnieje konflikt lokalny. Jest to łagodne założenie w wielu aplikacjach, np. przy alokacji kanałów bezprzewodowych, zwykle uzasadnione jest założenie, że stacja będzie w stanie wykryć, czy inne zakłócające nadajniki używają tego samego kanału (np. poprzez pomiar SINR). Ta informacja wyczuwająca jest wystarczająca, aby umożliwić algorytmom opartym na uczących się automatach znalezienie odpowiedniego kolorowania grafu z prawdopodobieństwem jeden.

Złożoność obliczeniowa

Kolorowanie wykresu jest trudne obliczeniowo. Decydowanie, czy dany graf dopuszcza k -kolorowanie dla danego k jest NP-zupełne, z wyjątkiem przypadków k ∈ {0,1,2} . W szczególności NP-trudno jest obliczyć liczbę chromatyczną. Problem 3-kolorowania pozostaje NP-zupełny nawet na 4-regularnych grafach planarnych . Jednak dla każdego k > 3 istnieje k -kolorowanie grafu płaskiego zgodnie z twierdzeniem o czterech kolorach i możliwe jest znalezienie takiego kolorowania w czasie wielomianowym.

Najbardziej znany algorytm aproksymacyjny oblicza kolorowanie rozmiaru co najwyżej w zakresie współczynnika O( n (log log  n ) ² (log n) ^-3 ) liczby chromatycznej. Dla wszystkich ε  > 0, przybliżenie liczby chromatycznej w zakresie n ^{1- ε} jest NP-trudne .

Jest również NP-trudne do pokolorowania 3-kolorowalnego wykresu z 4 kolorami i k- kolorowalnego wykresu z k ^{(log k  )/25} kolorów dla wystarczająco dużej stałej k .

Obliczanie współczynników wielomianu chromatycznego to #P-hard . W rzeczywistości, nawet obliczenie wartości jest #P-trudne w dowolnym punkcie wymiernym k z wyjątkiem k  = 1 i k  = 2. Nie ma FPRAS do oceny wielomianu chromatycznego w dowolnym punkcie wymiernym k  ≥ 1,5 z wyjątkiem k  = 2, chyba że NP  =  RP . ${\ Displaystyle \ chi (G, k)}$

W przypadku kolorowania krawędzi dowód wyniku Vizing daje algorytm, który używa co najwyżej Δ+1 kolorów. Jednak decydowanie między dwiema wartościami kandydackimi dla liczby chromatycznej krawędzi jest NP-zupełne. Jeśli chodzi o algorytmy aproksymacyjne, algorytm Vizinga pokazuje, że liczbę chromatyczną krawędzi można aproksymować z dokładnością do 4/3, a wynik twardości pokazuje, że nie  istnieje algorytm (4/3 −  ε ) dla żadnego ε > 0, chyba że P = NP . Są to jedne z najstarszych wyników w literaturze dotyczących algorytmów aproksymacyjnych, mimo że żaden artykuł nie używa wprost tego pojęcia.

Aplikacje

Planowanie

Modele kolorowania wierzchołków do szeregu problemów z planowaniem . W najczystszej postaci dany zestaw zadań musi być przypisany do przedziałów czasowych, każde zadanie wymaga jednego takiego przedziału. Zadania można planować w dowolnej kolejności, ale pary zadań mogą pozostawać w konflikcie w tym sensie, że mogą nie być przypisane do tego samego przedziału czasowego, na przykład dlatego, że oba korzystają ze współdzielonego zasobu. Odpowiedni wykres zawiera wierzchołek dla każdego zadania i krawędź dla każdej sprzecznej pary zadań. Liczba chromatyczna wykresu jest dokładnie minimalnym haszpanem , optymalnym czasem do zakończenia wszystkich zadań bez konfliktów.

Strukturę grafu określają szczegóły problemu szeregowania. Na przykład, podczas przypisywania samolotów do lotów, wynikowy wykres konfliktu jest wykresem interwałowym , dzięki czemu problem kolorowania można skutecznie rozwiązać. W przydziale pasma do stacji radiowych, wynikowy wykres konfliktu jest jednostkowym wykresem dyskowym , więc problem kolorowania jest 3 przybliżony.

Przydział rejestru

Kompilator to program komputerowy , który tłumaczy jeden język komputera do drugiego. Aby skrócić czas wykonania powstałego kodu, jedną z technik optymalizacji kompilatora jest alokacja rejestrów , gdzie najczęściej używane wartości kompilowanego programu są przechowywane w rejestrach szybkiego procesora . W idealnym przypadku wartości są przypisane do rejestrów, aby wszystkie mogły znajdować się w rejestrach, gdy są używane.

Podręcznikowe podejście do tego problemu polega na modelowaniu go jako problemu kolorowania grafów. Kompilator konstruuje wykres interferencji , w którym wierzchołki są zmiennymi, a krawędź łączy dwa wierzchołki, jeśli są potrzebne w tym samym czasie. Jeżeli wykres można pokolorować k kolorów, to dowolny zestaw zmiennych potrzebnych w tym samym czasie może być przechowywany w co najwyżej k rejestrów.

Inne aplikacje

Problem kolorowania wykresu pojawia się w wielu praktycznych obszarach, takich jak dopasowywanie wzorców , planowanie sportowe, projektowanie planów miejsc siedzących, planowanie egzaminów, planowanie taksówek i rozwiązywanie łamigłówek Sudoku .

Inne kolory

Teoria Ramseya

Ważną klasę problemów z niewłaściwym kolorowaniem bada się w teorii Ramseya , gdzie krawędzie grafów są przypisywane do kolorów i nie ma ograniczeń co do kolorów krawędzi padających. Prostym przykładem jest twierdzenie o przyjaźni , które mówi, że w każdym kolorowaniu krawędzi pełnego grafu sześciu wierzchołków będzie trójkąt monochromatyczny; często ilustruje to stwierdzenie, że każda grupa sześciu osób ma albo trzech wzajemnych nieznajomych, albo trzech wspólnych znajomych. Teoria Ramseya zajmuje się uogólnieniami tej idei w celu poszukiwania regularności wśród nieporządku, znajdowania ogólnych warunków istnienia podgrafów monochromatycznych o zadanej strukturze. ${\ Displaystyle K_ {6}}$

Inne kolory

Kolorowanie można również rozważyć dla grafów ze znakiem i grafów wzmocnienia .

Zobacz też

• Wykres krytyczny
• Wykres homomorfizmu
• Budowa Hajós
• Matematyka Sudoku
• Wykres wieloczęściowy
• Wyjątkowo kolorowy wykres
• Gra kolorowania wykresów

Uwagi

Bibliografia

Zewnętrzne linki

• High-Performance Graph Colouring Algorithms Zestaw 8 różnych algorytmów (zaimplementowany w C++) wykorzystany w książce A Guide to Graph Colouring: Algorithms and Applications (Springer International Publishers, 2015).
• Strona do kolorowania wykresów autorstwa Josepha Culbersona (programy do kolorowania wykresów)
• KOLORACJA autorstwa Jima Andrewsa i Mike'a Fellowsa to graficzna układanka do kolorowania
• Linki do kodów źródłowych do kolorowania wykresów
• Kod do wydajnego obliczania wielomianów Tutte, Chromatic i Flow autorstwa Gary'ego Haggarda, Davida J. Pearce'a i Gordona Royle'a
• Wykres kolorowania aplikacji internetowej autorstwa Jose Antonio Martina H.