Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
14
1.KLASYCZNEKOLOROWANIEGRAFÓW
MetodaRSI
MetodaRSIstanowioczywistąmodyfikacjęmetodyRS,polegającąna
wprowadzeniuopisywanegowcześniejmechanizmuwymianykolorów
(ang.interchange).Metodatamożebyćtraktowana,podobniejakRS,
jakoogólnywyznacznikzachowaniasięmetodsekwencyjnychzwymianą
kolorównadanejklasiegrafów.Ponieważprocedurawymianykolorów
możezostaćzaimplementowanatak,abydziałaławczasieO(m),ako-
lorowaniezachłannewczasieO(n),więccałyalgorytmbędziedziałać
wczasieO(mn).
algorytmKolorujRSI(G);
begin
K:=losowasekwencjawierzchołkówgrafuG;
KolorujZWymianą(G,K);
end;
FunkcjadobrocialgorytmuRSI(n)=O(n).Pierwszygrafdośćtrudny
dlaRSIpodaliSysłoiin.[30].Graftenbyłrzędu45izostałznalezio-
nyprzyprzeglądaniugrafówlosowychzapomocąposzukiwańkompu-
terowych.GrafemSHCdlatejmetodyjestgrafpokazanynarys.1.9,
natomiastgrafHCnieistnieje,podobniejakwprzypadkumetodyRS.
RYSUNEK1.9.Najmniejszygrafdośćtrudny
dlametodyRSI
MetodaLFI
MetodatajestmodyfikacjąmetodyLF,polegającąnazastosowaniupro-
cedurywymianykolorów.PodobniejakRSI,algorytmLFImożezostać
zaimplementowanytak,bydziałałwczasieO(mn).
algorytmKolorujLFI(G);
begin
K:=wierzchołkiGuporządkowanewgnierosnącychstopniwgrafieG;
KolorujZWymianą(G,K);
end;
Najmniejszegrafytrudnedokolorowaniadlatejmetodyprzedstawio-
nonarys.1.10.
