Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.KLASYCZNEKOLOROWANIEWIERZCHOŁKÓW
15
RYSUNEK1.10.(a)NajmniejszygrafdośćtrudnydlametodyLFI,
(b)najmniejszygraftrudnydlametodyLFI
MetodaSLI
MetodatajestmodyfikacjąmetodySL,analogicznądoLFI.Podobniejak
obieomówionepoprzedniometody,wykorzystującewymianękolorów,
możezostaćzaimplementowanatak,bydziałaławczasieO(mn).
algorytmKolorujSLI(G);
begin
K:=/
whileV\K/=/
0;
0do
dopiszdoKwierzchołekυonajmniejszymstopniuwpodgrafie
generowanymprzezV\K;
KolorujZWymianą(G,K);
end;
GrafySHC(SLI)iHC(SLI)pokazanonarys.1.11.
RYSUNEK1.11.(a)NajmniejszygrafdośćtrudnydlametodySLI,
(b)najmniejszygraftrudnydlametodySLI
MetodaCS
Metodatajesttypowymalgorytmemsekwencyjnym.Jejnazwapochodzi
odterminuangielskiegoConnectedSequential(CS).Metodaopierasięna
obserwacji,żedokolorowanianależywybieraćwierzchołkisąsiedniedo
jużpokolorowanych,copozwalaunikaćnp.błędnegokolorowaniagrafów
taktrywialnychjakścieżkaP4.
