Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.KLASYCZNEKOLOROWANIEWIERZCHOŁKÓW
11
forυ:=υ1toυndo
przydzielυnajniższylegalnykolorwgrafieG;
end;
DEFINICJA1.22.SekwencyjnymalgorytmemkolorowaniagrafuGbędzie-
mynazywaćalgorytmdziałającywdwóchnastępującychkrokach:
1.UstalpewnąkolejnośćKkolorowaniawierzchołkówgrafuG.
2.KolorujZachłannie(G,K).
Wymianakolorówjeststosunkowoprostymsposobempoprawyefek-
tywnościdowolnegoalgorytmusekwencyjnego.Metodatazostałaprzed-
stawionawopracowaniu[26].Wynikaonaznastępującegospostrzeżenia:
jeżeliwkolejnymkrokudopokolorowaniawierzchołkaυkjestwymagany
nowykolor,tobyćmożejestmożliwatakazamianakolorówwktórymś
zdwubarwnychpodgrafówgrafuG,byzwolnićjedenzużytychdotąd
kolorów.
algorytmKolorujZWymianą(G,K);
begin
forυ:=υ1toυndobegin
ifυwymaganowegokoloruthen
spróbujdokonaćwymianyprzydzielonychdotądkolorówwG,tak
abyzwolnićjedenzkolorówdlaυ;
przydzielυnajniższylegalnykolorwgrafieG;
end
end;
MetodaRS
MetodaRS,nazywanainaczejnaiwną,jestmetodąsekwencyjną,wktórej
niemaetapuporządkowaniawierzchołków.Mówiącinaczej,wierzchołki
sąporządkowanewsposóblosowy.Jejnazwapochodziodangielskiego
terminuRandomSequential(RS).Metodatamożebyćtraktowanajako
ogólnywyznacznikzachowaniasięmetodsekwencyjnychnadanejklasie
grafów.
algorytmKolorujRS(G);
begin
K:=losowasekwencjawierzchołkówgrafuG;
KolorujZachłannie(G,K);
end;
MetodaRSmożezostaćzaimplementowanawczasieproporcjonalnym
dorozmiarugrafuG,toznaczyO(m+n).Analizędobrocitejmetodymoż-
naprzeprowadzićwykorzystującrodzinęgrafówdwudzielnychJohnsona
