Chciwy kolorowanie - Greedy coloring

Dwa zachłanne kolorowania tego samego wykresu korony przy użyciu różnych porządków wierzchołków. Prawy przykład uogólnia na wykresy dwukolorowe z n wierzchołkami, gdzie algorytm zachłanny zużywa n /2 kolorów.

W badaniu barwienia wykres problemów matematycznych i informatyczne , na chciwego barwienia lub sekwencyjnego zabarwienia jest zabarwienie wierzchołków o wykresem utworzonym przez chciwego algorytmu , który uważa wierzchołków grafu sekwencji i przydziela każdemu wierzchołka jej pierwszej dostępnych kolorów . Barwniki zachłanne można znaleźć w czasie liniowym, ale generalnie nie wykorzystują one minimalnej możliwej liczby kolorów.

Różne wybory sekwencji wierzchołków zwykle powodują różne zabarwienia danego wykresu, więc wiele badań nad zachłannymi kolorowaniami dotyczyło znalezienia dobrego uporządkowania. Zawsze istnieje uporządkowanie, które daje optymalne zabarwienie, ale chociaż takie uporządkowania można znaleźć dla wielu specjalnych klas grafów, ogólnie trudno je znaleźć. Powszechnie stosowane strategie porządkowania wierzchołków obejmują umieszczanie wierzchołków wyższego stopnia wcześniej niż wierzchołki niższego stopnia lub wybieranie wierzchołków z mniejszą liczbą dostępnych kolorów zamiast wierzchołków, które są mniej ograniczone.

Odmiany zachłannej kolorystyki wybierają kolory w sposób online , bez znajomości struktury niebarwionej części wykresu, lub wybierają inne kolory niż pierwszy dostępny w celu zmniejszenia całkowitej liczby kolorów. Algorytmy zachłannego kolorowania zostały zastosowane w problemach planowania i alokacji rejestrów , analizie gier kombinatorycznych oraz dowodach innych wyników matematycznych, w tym twierdzenia Brooksa o związku między kolorowaniem a stopniem. Inne pojęcia w teorii grafów wywodzące się z zachłannych kolorowań obejmują liczbę Grundy'ego na wykresie (największą liczbę kolorów, jaką można znaleźć przy zachłannym kolorowaniu) oraz dobrze pokolorowane wykresy , dla których wszystkie zachłanne kolorowania używają tej samej liczby zabarwienie.

Algorytm i złożoność

Zachłanne kolorowanie dla danej kolejności wierzchołków można obliczyć za pomocą algorytmu, który działa w czasie liniowym w odniesieniu do liczby wierzchołków i krawędzi w grafie. Algorytm przetwarza wierzchołki w podanej kolejności i kolejno każdemu z nich przypisuje kolor. Kolory mogą być reprezentowane przez liczby , a każdy wierzchołek otrzymuje kolor o najmniejszej liczbie, który nie jest jeszcze używany przez jednego z jego sąsiadów. ${\displaystyle 0,1,2,\kropki}$

Wydajnym sposobem określenia najmniejszego dostępnego koloru dla wierzchołka jest użycie tablicy zmiennych logicznych o nazwie . Początkowo wszystkie elementy są ustawione na False. Biorąc pod uwagę bezbarwne wierzchołek , możemy teraz rozważyć wszystkie sąsiadów o , a jeśli został już przypisany do koloru , to jest ustawiona na wartość true. W następnym kroku skanujemy, aby zidentyfikować pierwszy Fałszywy element. Indeks tego elementu odpowiada najniższemu możliwemu kolorowi dla . Wreszcie, wszystkie elementy muszą zostać ustawione z powrotem na False. ${\używany styl wyświetlania}$${\używany styl wyświetlania}$${\displaystyle v}$${\ Displaystyle u}$${\displaystyle v}$${\ Displaystyle u}$${\displaystyle j}$${\ Displaystyle używany[j]}$${\używany styl wyświetlania}$${\displaystyle v}$${\używany styl wyświetlania}$

W Pythonie ten algorytm można wyrazić w następujący sposób. Przykładowy przebieg przy użyciu małego wykresu znajduje się na dole kodu:

def get_first_feasible_color(v, G, used, c):
	for u in G[v]:
		if c[u] != -1:
			used[c[u]] = True
	for j in range(len(used)):
		if used[j] == False:
			break
	for u in G[v]:
		if c[u] != -1:
			used[c[u]] = False
	return j
	
def greedy_color(G, order):
	#Determines a greedy coloring of the graph G in the order given by the list "order"
	c = [-1 for i in range(len(G))]
	used = [False for i in range(len(G))]
	for v in order:
		c[v] = get_first_feasible_color(v, G, used, c)
	return c

"""
An example run of the greedy algorithm for graph coloring. Here, the vertices of the graph
assume the labels 0, 1, 2, .... The graph G is then represented by an adjacency list.
This means that G[v] defines a list containing the neighbors of vertex v. 
	
In the following example, G is a cycle graph on five vertices. The vertex order is simply
[0, 1, 2, 3, 4]. The return value of the greedy_color procedure is a list where c[v]
gives the color of vertex v. Colors use the labels 0, 1, 2, upwards.
"""
G = [[1, 4], [0, 2], [1, 3], [2, 4], [0, 3]]
order = [0, 1, 2, 3, 4]
c = greedy_color(G, order)
print(c)

Korzystając z podanego przykładu, ten kod generuje dane wyjściowe . Jest to interpretowane jako przypisanie wierzchołka 0 do koloru 0; wierzchołek 1 jest przypisany do koloru 1; wierzchołek 2 jest przypisany do koloru 0; wierzchołek 3 jest przypisany do koloru 1; a wierzchołek 4 jest przypisany do koloru 2. Rozwiązanie wykorzystuje zatem ogólnie trzy kolory. ${\ Displaystyle [0,1,0,1,2]}$

W tym kodzie procedura get_first_feasible_colorzajmuje czas proporcjonalny do liczby sąsiadów . Dzieje się tak, ponieważ wykonuje dwie pętle na zbiorze sąsiadów i jedną pętlę, aby zidentyfikować odpowiedni kolor (ta ostatnia wykona maksymalnie kroki, gdzie jest liczba wierzchołków tego sąsiada ). Ponadto należy najpierw ustawić wszystkie wierzchołki jako niepokolorowane (używając tutaj etykiety koloru -1), a wszystkie elementy na False. Cały algorytm ma zatem złożoność polegającą na tym, że gdzie jest liczba wierzchołków na grafie i jest liczbą krawędzi na grafie. ${\displaystyle v}$${\displaystyle x+1}$${\displaystyle x}$${\displaystyle v}$greedy_color${\używany styl wyświetlania}$${\ Displaystyle O (n + m)}$${\ Displaystyle n}$${\ Displaystyle m}$

Wybór zamówienia

Różne uporządkowanie wierzchołków wykresu może spowodować, że zachłanne kolorowanie będzie wykorzystywało różne liczby kolorów, od optymalnej liczby kolorów do, w niektórych przypadkach, liczby kolorów proporcjonalnej do liczby wierzchołków na wykresie. Na przykład, wykres korony (wykres utworzony z dwóch zestawów rozłącznych o n / 2 wierzchołków { a ₁ , z ₂ , ... } i { b ₁ , b ₂ , ... }, łącząc _I z b _J WHENEVER i ≠ j ) może być szczególnie złym przypadkiem dla zachłannego kolorowania. Przy porządkowaniu wierzchołków a ₁ , b ₁ , a ₂ , b ₂ , ... , zachłanne kolorowanie użyje n /2 kolorów, po jednym dla każdej pary ( a _i , b _i ) . Jednak optymalna liczba kolorów dla tego wykresu to dwa, jeden kolor dla wierzchołków a _i drugi dla wierzchołków b _i . Istnieją również grafy takie, że z dużym prawdopodobieństwem losowo wybrane uporządkowanie wierzchołków prowadzi do liczby kolorów znacznie większej niż minimum. Dlatego w zachłannym kolorowaniu ważne jest, aby starannie dobrać kolejność wierzchołków.

Dobre zamówienia

Wierzchołki dowolnego grafu można zawsze uporządkować w taki sposób, aby algorytm zachłanny dawał optymalne zabarwienie. Ponieważ przy danym optymalnym zabarwieniu wierzchołki można uporządkować według ich kolorów. Następnie, gdy użyje się algorytmu zachłannego o tej kolejności, wynikowe zabarwienie jest automatycznie optymalne. Ponieważ jednak optymalne kolorowanie grafów jest NP-zupełne , każdy podproblem, który pozwoliłby na szybkie rozwiązanie tego problemu, w tym znalezienie optymalnego uporządkowania zachłannego kolorowania, jest NP-trudny .

W grafach interwałowych i grafach akordowych , jeśli wierzchołki są uporządkowane odwrotnie do porządku eliminacji doskonałej , to wcześniejsi sąsiedzi każdego wierzchołka utworzą klikę . Ta właściwość powoduje, że zachłanne kolorowanie daje optymalne zabarwienie, ponieważ nigdy nie używa więcej kolorów niż jest to wymagane dla każdej z tych klik. Kolejność eliminacji można znaleźć w czasie liniowym, jeśli istnieje.

Co więcej, każde uporządkowanie doskonałej eliminacji jest dziedzicznie optymalne , co oznacza, że ​​jest optymalne zarówno dla samego grafu, jak i dla wszystkich jego indukowanych podgrafów . Te doskonale zamawiane wykresy (obejmujące akordowe wykresy , wykresy porównywalności i międzymiastowych-dziedziczna wykresy ) są definiowane jako wykresy, które mają dziedzicznie optymalną kolejność. Rozpoznawanie doskonale uporządkowanych grafów jest również NP-zupełne.

Złe zamówienia

Liczba kolorów wytworzonych przez zachłanne kolorowanie dla najgorszego uporządkowania danego wykresu nazywana jest liczbą Grundy'ego . Podobnie jak znalezienie dobrego uporządkowania wierzchołków dla zachłannego kolorowania jest trudne, tak samo znalezienie złego uporządkowania wierzchołków jest trudne. NP-zupełne jest określenie, dla danego grafu G i liczby k , czy istnieje kolejność wierzchołków G, która powoduje, że algorytm zachłanny używa k lub więcej kolorów. W szczególności oznacza to, że trudno znaleźć najgorsze uporządkowanie dla G .

Wykresy, dla których kolejność nie ma znaczenia

W wybarwione wykresy są wykresy dla których wszystkie barwniki wierzchołków tak dużej liczby kolorów. Ta liczba kolorów na tych wykresach jest równa zarówno liczbie chromatycznej, jak i liczbie Grundy'ego. Obejmują one cographs , które są dokładnie tymi wykresami, w których wszystkie indukowane podwykresy są dobrze pokolorowane. Jednak ustalenie, czy wykres jest dobrze pokolorowany , jest współ-NP-zupełne .

Jeśli losowy graf zostanie wylosowany z modelu Erdősa-Rényi ze stałym prawdopodobieństwem uwzględnienia każdej krawędzi, to każda kolejność wierzchołków wybrana niezależnie od krawędzi grafu prowadzi do kolorowania, którego liczba kolorów jest zbliżona do dwukrotności wartości optymalnej, z dużą prawdopodobieństwo . Nie wiadomo, czy istnieje metoda wielomianowa pozwalająca na znalezienie znacznie lepszych podbarwień tych wykresów.

Degeneracja

Trójkątny pryzmat i kwadratowy antypryzmat, wykresy, których zachłanne zabarwienia przy użyciu porządkowania degeneracji dają większą niż optymalna liczbę kolorów

Ponieważ trudno jest znaleźć optymalne uporządkowanie wierzchołków, zastosowano heurystyki, które mają na celu zmniejszenie liczby kolorów, nie gwarantując jednocześnie optymalnej liczby kolorów. Powszechnie stosowanym porządkowaniem zachłannego kolorowania jest wybranie wierzchołka v o minimalnym stopniu , uporządkowanie podgrafu z v usuniętym rekurencyjnie , a następnie umieszczenie v na końcu w porządkowaniu. Największy stopień usuniętego wierzchołka napotkany przez ten algorytm nazywa się degeneracją grafu, oznaczoną d . W kontekście zachłannego kolorowania ta sama strategia porządkowania nazywana jest również najmniejszym ostatnim porządkowaniem. To uporządkowanie wierzchołków i degenerację można obliczyć w czasie liniowym. Można go postrzegać jako ulepszoną wersję wcześniejszej metody porządkowania wierzchołków, sortowania od największego do pierwszego, która sortuje wierzchołki w porządku malejącym według ich stopni.

Przy porządkowaniu degeneracji, zachłanne zabarwienie będzie wykorzystywało co najwyżej kolory d  +1 . Dzieje się tak dlatego, że po pokolorowaniu każdy wierzchołek będzie miał co najwyżej d już kolorowych sąsiadów, więc jeden z pierwszych kolorów d  +1 będzie wolny do użycia. Kolorowanie zachłanne z porządkowaniem degeneracji może znaleźć optymalne kolory dla pewnych klas grafów, w tym drzew, pseudolasów i grafów koron. Markossian, Gasparian i przekaźnik (1996) określić wykres być -perfect jeśli na a co indukowana subgraph z liczba chromatyczna równa degeneracji plus jeden. Dla tych grafów algorytm zachłanny z porządkowaniem degeneracji jest zawsze optymalny. Każdy -idealny graf musi być grafem o parzystych dziurach , ponieważ parzyste cykle mają chromatyczną liczbę dwa i degenerację dwa, nie pasujące do równości w definicji -doskonałego grafu. Jeśli graf i jego graf dopełnienia są wolne od parzystych dziur, oba są -idealne. Wykresy, które są zarówno wykresami idealnymi, jak i wykresami -perfect, są dokładnie wykresami akordowymi . Na wykresach parzystych bez dziur, bardziej ogólnie, kolejność degeneracji przybliża optymalne zabarwienie z dokładnością do co najwyżej dwukrotności optymalnej liczby kolorów; to znaczy, że jego stosunek aproksymacji wynosi 2. Na grafach dysków jednostkowych jego stosunek aproksymacji wynosi 3. Pryzmat trójkątny jest najmniejszym grafem, dla którego jedno z jego porządków degeneracji prowadzi do nieoptymalnego zabarwienia, a antypryzmat kwadratowy jest najmniejszym grafem, który nie może być optymalnie zabarwiony przy użyciu żadnego z jego zdegenerowanych porządków. ${\ Displaystyle G}$${\ Displaystyle \ beta}$${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle \ beta}$${\ Displaystyle \ beta}$${\ Displaystyle \ beta}$${\ Displaystyle \ beta}$

Zamówienia adaptacyjne

Brélaz (1979) zaproponował strategię, zwaną DSatur , dla porządkowania wierzchołków w zachłannym kolorowaniu, która przeplata konstrukcję porządkowania z procesem kolorowania. W tej wersji algorytmu zachłannego kolorowania następny wierzchołek do pokolorowania na każdym kroku jest wybierany jako ten z największą liczbą różnych kolorów w jego sąsiedztwie . W przypadku wiązań, z wierzchołków wiązanych wybierany jest wierzchołek o maksymalnym stopniu w podgrafie niepokolorowanych wierzchołków. Ogólna złożoność tego podejścia jest , chociaż lepszą wydajność dla rzadkich grafów można osiągnąć przy użyciu implementacji, w której jest liczbą wierzchołków w grafie i liczbą krawędzi. ${\ Displaystyle O (n ^ {2})}$${\ Displaystyle O ((n + m) \ log n)}$${\ Displaystyle n}$${\ Displaystyle m}$

Ta metoda pozwala znaleźć optymalne kolory dla grafów dwudzielnych ,, kaktusowych , kołowych , cyklicznych , wszystkich grafów na co najwyżej sześciu wierzchołkach. Chociaż Lévêque i Maffray (2005) początkowo twierdzili, że ta metoda znajduje optymalne kolory dla grafów Meyniela , później znaleźli kontrprzykład dla tego twierdzenia.

Alternatywne schematy doboru kolorów

Możliwe jest zdefiniowanie odmian algorytmu zachłannego kolorowania, w którym wierzchołki danego grafu są pokolorowane w określonej kolejności, ale w którym kolor wybrany dla każdego wierzchołka niekoniecznie jest pierwszym dostępnym kolorem. Należą do nich metody, w których niezabarwiona część grafu jest nieznana algorytmowi lub w których algorytm ma pewną swobodę w dokonywaniu lepszych wyborów kolorowania niż zrobiłby to podstawowy algorytm zachłanny.

Wybór online

Alternatywne strategie wyboru kolorów zostały zbadane w ramach algorytmów internetowych . W problemie kolorowania grafów online, wierzchołki grafu są przedstawiane pojedynczo w dowolnej kolejności algorytmowi kolorowania; algorytm musi wybrać kolor dla każdego wierzchołka, bazując tylko na kolorach i sąsiedztwach między już przetworzonymi wierzchołkami. W tym kontekście mierzy się jakość strategii wyboru kolorów przez jej konkurencyjność , stosunek liczby użytych kolorów do optymalnej liczby kolorów dla danego wykresu.

Jeśli nie podano dodatkowych ograniczeń na wykresie, optymalny stosunek konkurencyjności jest tylko nieznacznie subliniowy. Jednak w przypadku wykresów przedziałowych możliwy jest stały stosunek współzawodnictwa, podczas gdy dla wykresów dwudzielnych i wykresów rzadkich można osiągnąć stosunek logarytmiczny. Rzeczywiście, w przypadku rzadkich grafów standardowa strategia zachłannego kolorowania polegająca na wybraniu pierwszego dostępnego koloru osiąga ten konkurencyjny współczynnik i możliwe jest udowodnienie dopasowania dolnego ograniczenia współczynnika konkurencyjnego dowolnego algorytmu kolorowania online.

Skromna kolorystyka

Oszczędne barwiących , dla danego wykresu i wierzchołek kolejności, zostały zdefiniowane jako zabarwienie wytwarzać chciwego algorytmu kolory wierzchołkami w podanej kolejności, a dopiero wprowadza nowy kolor, gdy wszystkie poprzednie kolory przylegają do danego wierzchołka ale może wybrać kolor do użycia (zamiast zawsze wybierać najmniejszy), gdy jest w stanie ponownie użyć istniejącego koloru. Nakazał liczba chromatyczna jest najmniejsza liczba kolorów, które można uzyskać dla danego zamawiającego w ten sposób, a liczba ochromatic jest największym nakazał liczba chromatyczna spośród wszystkich barwników wierzchołków danego grafu. Mimo odmiennej definicji liczba ochromatyczna zawsze równa się liczbie Grundy'ego.

Aplikacje

Ponieważ jest szybki i w wielu przypadkach może używać kilku kolorów, zachłanne kolorowanie może być używane w aplikacjach, w których potrzebne jest dobre, ale nie optymalne kolorowanie wykresu. Jednym z wczesnych zastosowań algorytmu zachłannego było rozwiązanie problemów takich jak planowanie kursów, w którym zbiór zadań musi być przypisany do danego zestawu przedziałów czasowych, aby uniknąć przypisania niezgodnych zadań do tego samego przedziału czasowego. Może być również używany w kompilatorach do alokacji rejestrów , poprzez zastosowanie go do grafu, którego wierzchołki reprezentują wartości, które mają być przypisane do rejestrów i których krawędzie reprezentują konflikty między dwiema wartościami, których nie można przypisać do tego samego rejestru. W wielu przypadkach te wykresy interferencji są wykresami akordowymi , co pozwala na zachłanne kolorowanie w celu uzyskania optymalnego przypisania rejestrów.

W kombinatorycznej teorii gier dla bezstronnej gry podanej w formie jawnej jako skierowany graf acykliczny, którego wierzchołki reprezentują pozycje w grze, a krawędzie reprezentują prawidłowe ruchy z jednej pozycji do drugiej, algorytm zachłannego kolorowania (stosujący odwrotność topologicznego uporządkowania grafu ) oblicza wartość nim każdej pozycji. Wartości te można wykorzystać do określenia optymalnej gry w dowolnej pojedynczej grze lub dowolnej rozłącznej sumie gier.

W przypadku wykresu o maksymalnym stopniu Δ , każde zachłanne kolorowanie będzie używać co najwyżej Δ + 1 kolorów. Twierdzenie Brooksa mówi, że z dwoma wyjątkami ( klik i nieparzyste cykle ) potrzebne są najwyżej Δ kolorów. Jeden dowód twierdzenia Brooksa polega na znalezieniu kolejności wierzchołków, w której pierwsze dwa wierzchołki sąsiadują z końcowym wierzchołkiem, ale nie sąsiadują ze sobą, a każdy wierzchołek inny niż ostatni ma co najmniej jednego późniejszego sąsiada. W przypadku zamówienia z tą właściwością algorytm zachłannego kolorowania używa co najwyżej Δ kolorów.

Uwagi

Zewnętrzne linki

• Wysokowydajne algorytmy kolorowania grafów Zestaw algorytmów kolorowania grafów (zaimplementowany w C++) wykorzystany w książce A Guide to Graph Colouring: Algorithms and Applications (Springer International Publishers, 2021).

Bibliografia