Strona główna

1. Klasyczne kolorowanie grafów


Pobieranie 25.83 Kb.
Data18.06.2016
Rozmiar25.83 Kb.
1.Klasyczne kolorowanie grafów

Wstęp

Klasyczne kolorowanie wierzchołków grafu jest problemem NP trudnym. Duża złożoność obliczeniowa problemu wymusza stosowanie heurystycznych metod przybliżonych w celu znalezienia rozwiązań suboptymalnych w czasie wielomianowym. W pierwszej części swojej pracy pragnę przedstawić prosty program kolorujący grafy dwoma algorytmami: Zachłannym i LF. Program zawiera dosyć prymitywny interface użytkownika, jednak jego zaletą jest ogólna przejrzystość i funkcjonalność. Główną funkcją programu jest funkcja sterująca Graf_zrob() która jako wartość zwraca macierz Graf będącą macierzą sąsiedztwa grafu nieskierowanego poddawanego działaniu algorytmu. Kod głównej funkcji wygląda następująo:


function Graf = Graf_zrob()

n = input('podaj liczbe wierzcholkow w grafie\n');


// dokonujemy wyboru ilości wierzchołków w grafie. Przyjmujmy ze wierzchołki będą miały

// numery od 1-n


for j=1:n

Graf(j,j)=0;



end

wybor=1;


lk=1;

while(wybor==1)

wybor = input('0) Graf ukończony\n1)połacz wierzcholki\n');


// 0) akceptujemy dotychczas utworzony graf ,

// 1) łączymy dwa wybrane wierzchołki krawędzią
if(wybor==0)

disp('Dokonaj wyboru:')



end

if(wybor==1)

u = input('Podaj 1 wierzcholek ktory chcesz polaczyc\n');

v = input('Podaj 2 wierzcholek ktory chcesz polaczyc\n');

Graf(u,v)=1;

Graf(v,u)=1;

E(lk,:)=[u,v]

lk=lk+1;

end

end
// macierz E o wymiarach lk x 2 jest zbiorem par wierzchołków połączonych krawędzią,

// gdzie lk to liczba krawędzi w grafie.
// Poniżej znajduje się menu wyboru pomiędzy algorytmami
wybor = input('1)Alogrytm Zachlanny\n2)Algorytm LF\n');

if(wybor==1)

for j=1:n

K(j)=j;


end

Kolor = Zachlanny(Graf,K)



end

if(wybor==2)

Kolor=LF(Graf)



end


Algorytm zachłanny

Najbardziej popularnym algorytmem przybliżonym w kolorowaniu grafów jest algorytm zachłanny. Funkcja Zachlanny(Graf,K) jako argument pobiera graf Graf przedstawiony w formie macierzy sąsiedztwa. Drugim argumentem funkcji jest wektor kolejności wierzchołków K kolorowania grafu Graf. Dla algorytmu zachłannego przyjmujemy po prostu, że kolejność nie ma znaczenia (nic nie determinuje odpowiedniej kolejności) więc przyjmujemy że kolejność dla każdego j będzie wektorem K(j)=j. Algorytm działa wedle zasady: „ Przydzielaj każdemu z wierzchołków najmniejszy legalny kolor”. Oto kod źródłowy funkcji Zachlanny(Graf,K).


function Kolor = Zachlanny(Graf,K)

n=size(Graf);



for i=1:n

kolor=1;


Kol(i)=0;

for j=1:i

if(Kol(j)==kolor && Graf(K(i),K(j))==1)
// W tym momencie program sprawdza, czy można przydzielić kolor wierzchołkowi i //przydziela go jeśli do tej pory nie został przydzielony, jeśli został przydzielony czynność //powtarza dla kolor +1 .
kolor = kolor + 1;

j=0;


end

end

Kol(i)=kolor;



end

for i=1:n

Kolor(K(i))=Kol(i);



end




Na wyjściu otrzymujemy wektor Kolor pokolorowania grafu Graf. Jeżeli wierzchołek i został pokolorowany kolorem kolor to oznacza, że Kolor(i)=kolor. Wektor Kol jest wektorem pomocniczym i służy do segregacji kolorów dla przejrzystości na wyjściu. Przeanalizujmy działanie algorytmu na konkretnym przykładzie.










Powyższy graf jest grafem dwudzielnym, oznacza to że liczba chromatyczna jest równa 2. Stosując algorytm zachłanny otrzymamy wektor rozwiązania Kolor postaci :
1 1 2 2 3 3 4 4
Więc algorytm proponuje nam pokolorowanie nieoptymalne przy danej implementacji algorytmu zachłannego więc graf jest przynajmniej grafem dość trudnym dla algorytmu zachłannego. Nie można powiedzieć, że graf jest trudny dla algorytmu zachłannego, ponieważ dla innej numeracji wprowadzania wierzchołków otrzymamy rozwiązanie optymalne:






1 1 1 1 2 2 2 2


Analizując powyższy przykład dochodzi się do wniosku, że kolejność wprowadzenia wierzchołków do kolorowania ma istotny wpływ na pokolorowanie grafu.

Algorytm LF jako przykład algorytmu sekwencyjnego.

Sekwencyjnym algorytmem kolorowania grafu nazywamy algorytm ustalający pewną kolejność kolorowania wierzchołków grafu, następnie stosując algorytm zachłanny.

Przykładem algorytmu sekwencyjnego jest algorytm LF (Largest-First). Metoda ta jest rezultatem spostrzeżenia, że wierzchołki o niskim stopniu pozostawiają swobodę wyboru koloru. Metoda jest bardzo prosta i opiera się na uporządkowaniu wierzchołków wg nierosnących stopni w grafie, stosując następnie algorytm zachłanny. Oto implementacja algorytmu w środowisku Matlab, funkcja LF(Graf) uruchamia działanie algorytmu:
// Funkcja LF(Graf) rozpoczyna działanie, tworząc wektor N gdzie N(i) to jest stopień i –tego // wierzchołka
function Kolor = LF(Graf)

for i=1:size(Graf)

deq=0;


for j=1:size(Graf)

if (Graf(i,j)==1)

deq=deq+1;



end

end

N(i)=deq;



end
// tutaj następuje ustalenie kolejności K otrzymanej na podstawie wektora N.
i = 1;

while (i<=size(Graf))

A=find(N==max(N));

K(i)=A(1);

N(A(1))=-1;

i=i+1;

end

disp(K)


Kolor = Zachlanny(Graf,K);
Podczas analizy przykładu grafu z poprzedniego rozdziału, będącego grafem Johnsona nietrudno zauważyć, że algorytm LF dla każdego grafu Johnsona sprowadza się do algorytmu zachłannego. Nietrudno zauważyć, że każdy graf Johnsona w najgorszym przypadku wymaga użycia n/2 kolorów (gdzie n liczba wierzchołków). Dzieje się tak przy mojej implementacji dla pierwszego przykładu z rozdziału poprzedniego .Przeanalizujmy teraz zachowanie algorytmu dla poniższego grafu,:




Otrzymaliśmy następującą kolejność pobierania wierzchołków do kolorowania, odpowiadającą w tym przykładzie kolejności w algorytmie zachłannym:

1 2 3 4 5 6 7

I odpowiadające mu pokolorowanie:


Kolor = 1 1 2 3 4 2 2
Nie jest to optymalne pokolorowanie Grafu z rysunku ponieważ liczba chromatyczna grafu wynosi 3. (2,3,1,3,2,1,1) graf jest więc przynajmniej grafem dość trudnym.
Teza : „Graf „koperta” jest grafem trudnym dla algorytmu LF.

Dowód

Algorytm LF wymusza kolorowanie najpierw wierzchołków 1,2,3 (deq([1,2,3])=4) jednocześnie algorytm zachłanny przypisuje minimalny możliwy kolor do każdego z wierzchołków, więc zostaną wykorzystane na wierzchołki 1,2,3 dwa kolory. Oznacza to że kolorowane następnie dwa wierzchołki 4,5 (deq([4,5])=3) są połączone z wierzchołkami już pokolorowanymi wcześniej dwoma różnymi kolorami. Wymusza to nadanie trzeciego koloru wierzchołkom 4,5 , jednak wierzchołki 4,5 są połączone między sobą więc muszą być wykorzystane jeszcze dwa kolory, co daje w sumie 4 I kończy dowód.


Wnioski.
Algorytm LF mimo swojej prostoty jest algorytmem dosyć skutecznym. Sprawdza się zwłaszcza w przypadkach kiedy w grafie stopnie wierzchołków znacznie się różnią. Jednak przy grafach o równych stopniach (np. Grafy Johnsona) algorytm działa jak zwykły algorytm zachłanny.

Opis innych algorytmów sekwencyjnych



Poza wymienionym wyżej algorytmem LF kolorowania grafów istnieje jeszcze parę innych algorytmów sekwencyjnych dotyczących kolorowania klasycznego. Przykładem takiej metody jest algorytm KolorujZWymianą(G,K) opiera się on na spostrzeżeniu, że jeżeli wierzchołek v wymaga użycia nowego koloru, to może być możliwa wymiana koloru w którymś z dwubarwnych podgrafów grafu G, by zwolnić jeden z użytych dotąd kolorów. Innym sekwencyjnym algorytmem, jest algorytm RS(G), który pobiera losową sekwencję wierzchołków grafu G. Popularne są także mieszane algorytmy takie jak LFI(G) (funkcję Zachlanny(G,K) zastępuje się funkcją KolorujZWymianą(G,K) ), czy RSI(G) (po wybraniu losowej kombinacji wierzchołków stosuje się algorytm KolorujZWymianą(G,K). Problem kolorowania grafów nie ogranicza się tylko problemów klasycznych, ciekawymi problemami są także: problem kolorowania grafów on-line, oraz kolorowanie sprawiedliwe.


©snauka.pl 2016
wyślij wiadomość