Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.KLASYCZNEKOLOROWANIEWIERZCHOŁKÓW
13
MetodaSL
JesttometodasekwencyjnazaproponowanaprzezMatulęiin.[26]pod
oryginalnąnazwąSmallest-Last(SL).PodobniejakmetodaLFopierasię
onanaobserwacji,żewierzchołkiniemającewielusąsiadównależyko-
lorowaćjaknajpóźniej.Dziękipewnemuwyrafinowaniuwtworzeniuse-
kwencjiwierzchołkówdokolorowaniametodaSLjestpozbawionanie-
którychwadalgorytmuLF,np.optymalniekolorujedrzewa,cykle,grafy
unicykliczne,koła,grafydwudzielnepełne,grafyJohnsona[15]orazgra-
fyMycielskiego[27].Ponadtometodatakolorujegrafyk-zdegenerowane,
używającconajwyżejk+1kolorów.
Naprzykład,dlagrafówplanarnychmetodatazapewniaużycienie
więcejniż6kolorów.
algorytmKolorujSL(G);
begin
K:=/
whileV\K/=/
0;
0do
dopiszdoKwierzchołekυonajmniejszymstopniuwpodgrafie
generowanymprzezV\K;
KolorujZachłannie(G,K);{KoznaczaodwróceniekolejnościK}
end;
MetodaSLmożezostaćzaimplementowana,podobniejakpoprzednie,
wczasieO(m+n).DoanalizydobrocialgorytmuSLmożnawykorzystać
rodzinęgrafówdwudzielnych,zaproponowanąprzezColemanaiMore,a
[6].SkonstruowaneprzeznichgrafyCMkwnajgorszymprzypadkuwy-
magająk=n/6kolorów.StądfunkcjadobrociSL(n)=O(n).Grafem
SHCdlametodySLjestgrafnazywanypryzmą,pokazanynarys.1.8(a),
natomiastgrafemHCjestgrafnazywanypryzmatoidem,pokazanyna
rys.1.8(b).
RYSUNEK1.8.(a)PryzmaPm—najmniejszygrafdośćtrudnydlametodySL,
(b)pryzmatoidPd—najmniejszygraftrudnydlametodySL
