Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
16
1.KLASYCZNEKOLOROWANIEGRAFÓW
algorytmKolorujCS(G);
begin
K:=wierzchołkiGuporządkowane,takbykażdykolejny(zwyjątkiem
pierwszego)miałconajmniejjednegosąsiadawśródpoprzedzającychgo
wuporządkowaniu;
KolorujZachłannie(G,K);
end;
MetodaCSmożezostaćzaimplementowanawczasieO(m+n),np.
zwykorzystaniemtrawersowaniagrafutechnikąposzerzanialubpogłę-
biania.Analizadobrocitejmetodymożezostaćdokonanaidentyczniejak
analizadlaRS.StądmamyCS(n)=O(n).
RYSUNEK1.12.WachlarzF5—najmniejszygrafdość
trudnydlametodyCS
GrafemSHCdlatejmetodyjestwachlarzpokazanynarys.1.12,
natomiastnajmniejszygraftrudnydlatejmetodyniejestznany.Babel
iTinhofer[3]pokazali,żegrafnazywanydwasmoki,symbolicznieTD,
jestgrafemtrudnymdlaCS(patrzrys.1.13).
RYSUNEK1.13.DwasmokiTD—
najmniejszyznanygraftrudnydla
metodyCS
MetodaSLF
Metodataniejestmetodątypowosekwencyjną,gdyżzakładadynamiczne
porządkowaniewierzchołków.ZostałaonazaproponowanaprzezBr,
elaza
[4]podnazwąDSATURlubSaturationLF(SLF).Stanowionalogiczną
modyfikacjęmetodyLF,wynikającązfaktu,iżoswobodziewdoborze
kolorudlawierzchołkadecydujenieliczbasąsiadów,aleliczbaróżno-
barwnychsąsiadów.
algorytmKolorujSLF(G);
begin
