Nasycenie

Nasycenie

Klasa	Kolorowanie wykresów
Złożoność przestrzeni w najgorszym przypadku	Ο ( n 2 )

DSatur to algorytm kolorowania grafów zaproponowany przez Daniela Brélaza w 1979 roku. Podobnie jak algorytm zachłannego kolorowania , DSatur koloruje wierzchołki grafu jeden po drugim, dodając wcześniej nieużywany kolor w razie potrzeby. Po pokolorowaniu nowego wierzchołka algorytm określa, który z pozostałych niekolorowanych wierzchołków ma największą liczbę kolorów w swoim sąsiedztwie i koloruje ten wierzchołek jako następny. Brélaz definiuje tę liczbę jako stopień nasycenia danego wierzchołka. Skrócenie terminu „stopień nasycenia” tworzy nazwę algorytmu. DSatur to heurystyczny algorytm kolorowania grafów, który zapewnia dokładne wyniki dla wykresów dwudzielnych, cyklicznych i kołowych. W literaturze DSatur jest również określany jako nasycenie LF.

Pseudo kod

Niech „stopień nasycenia” wierzchołka będzie liczbą różnych kolorów używanych przez jego sąsiadów. Biorąc pod uwagę prosty , nieukierunkowany wykres ${\ Displaystyle 1,2,3,...}$ który zagraża zestawowi $sol$ i zestawowi krawędzi $,$$,$ kolory wszystkim wierzchołkom za pomocą kolorowych etykiet sol . Algorytm działa w następujący sposób:

1. Niech $bezbarwnym$ wierzchołkiem w najwyższym stopniu $.$ W przypadku powiązań wybierz wierzchołek spośród wierzchołków o największym stopniu w podgrafie indukowanym przez wierzchołki bez koloru.
2. Przypisz $etykietę o najniższym kolorze$ która nie jest używana przez żadnego z jej sąsiadów.
3. Jeśli wszystkie wierzchołki zostały pokolorowane, to koniec; w przeciwnym razie wróć do kroku 1.

Krok 2 tego algorytmu przypisuje kolory wierzchołkom przy użyciu tego samego schematu, co algorytm zachłannego kolorowania . Główne różnice między tymi dwoma podejściami pojawiają się w kroku 1 powyżej, gdzie wierzchołki postrzegane jako najbardziej „ograniczone” są kolorowane jako pierwsze.

Przykład

Wykres kołowy z siedmioma wierzchołkami i dwunastoma krawędziami

Rozważ wykres pokazany po prawej stronie. ${\ Displaystyle G = (V, E)}$ Jest to wykres kołowy i dlatego zostanie optymalnie pokolorowany przez algorytm DSatur. Wykonanie algorytmu powoduje wybranie i pokolorowanie wierzchołków w następujący sposób. (W tym przykładzie, gdy powiązania występują w obu heurystykach DSatur, wybierany jest wierzchołek z najniższym spośród nich etykietowaniem leksykograficznym.)

1. wierzchołek sol $\ displaystyle g}$ (kolor 1)
2. wierzchołek ${\ displaystyle a}$ (kolor 2)
3. wierzchołek ${\ displaystyle b}$ (kolor 3)
4. wierzchołek do $\ displaystyle c}$ (kolor 2)
5. wierzchołek ${\ displaystyle d}$ (kolor 3)
6. Wierzchołek mi $\ displaystyle e}$ (kolor 2)
7. wierzchołek ${\ displaystyle f}$ (kolor 3)

Daje to ostateczne trójkolorowe rozwiązanie $\ mathcal {S}} = \ {\ {g \}, \{a,c,e\},\{b,d,f\}\}}$ .

Wydajność

Najgorszy przypadek złożoności DSatur to $Displaystyle$ wierzchołków na wykresie $O (n ^ {2})}} Dzieje$$czasu , a proces ten$$,$ ponieważ proces wybierania następnego wierzchołka do pokolorowania zajmuje trochę przeprowadzany Algorytm można również zaimplementować przy użyciu sterty binarnej do przechowywania stopni nasycenia, działając w ${\ Displaystyle O ((n + m) \ log n)}$ gdzie ${\ displaystyle m}$ jest liczbą krawędzi w grafie. Daje to znacznie szybsze przebiegi z rzadkimi wykresami.

Wiadomo, że DSatur jest dokładny dla grafów dwudzielnych, a także dla wykresów cykli i kół. W porównaniu empirycznym przeprowadzonym przez Lewisa w 2021 r. DSatur dawał znacznie lepsze kolorowanie wierzchołków niż $,$ zachłanny losowych wykresach z prawdopodobieństwem krawędzi gdy z kolei dawał znacznie gorsze kolorowanie niż rekurencyjny największy pierwszy algorytm .

Linki zewnętrzne

• Wysokowydajne algorytmy kolorowania grafów Zestaw algorytmów kolorowania grafów (zaimplementowanych w C++) użyty w książce A Guide to Graph Colouring: Algorithms and Applications (Springer International Publishers, 2021).
• Implementacja algorytmu DSatur w języku C++ , przedstawiona w ramach artykułu The DSatur Algorithm for Graph Coloring , Geeks for Geeks (2021)