Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
10
1.KLASYCZNEKOLOROWANIEGRAFÓW
najwyżej∆(G),więcjeżelikażdyzjegosąsiadówmainnykolor,toza-
wszeistniejekolorwolnydlaυwpalecie∆(G)+1barw.
Istniejątylkodwieklasygrafów,dlaktórychoszacowanie(1.1)ma
postaćrówności.Brooks[5]udowodnił,żejesttakjedyniedlacykliC2k+1
orazgrafówpełnych.Wynikaztego,żejeżeliGniejestgrafempełnym
oraz∆(G)>3,to
χ(G)<∆(G).
(1.2)
Możnapodaćklasęgrafów,dlaktórychoszacowanie(1.2)jestbardzo
nieprecyzyjne.TakjestwprzypadkugwiazdSk=K1,k.Grafytakiesą
oczywiściedwubarwne,natomiastzoszacowaniawynikanierówność
χ(Sk)<k.
InneznaneoszacowaniegórneliczbychromatycznejgrafuGmapo-
stać
χ(G)<√2m+1.
(1.3)
DajeonomniejszegórneograniczeniedlawspomnianejklasygrafówK1,k,
aleidlategoograniczeniamożnapodaćklasygrafów,dlaktórychbłąd
oszacowaniajestdowolnieduży.Przykłademmogąbyćturównieżgwiaz-
dylubogólniej:grafypełnedwudzielne.
Opróczoszacowańogólnychistniejąjeszczemniejlubbardziejoczy-
wisteoszacowaniadlaszczególnychklasgrafów.Wystarczyprzypomnieć
najbardziejznanywynikwdziedziniekolorowaniagrafów,mianowicie,
żekażdygrafplanarnymożnapokolorować4kolorami[1,2].
Wpraktycestosunkowonajlepszymoszacowaniemliczbychromatycz-
nejodgórysąwynikidostarczaneprzezprzybliżonemetodykolorowania
grafów.
1.2.2.
Najczęściejspotykanemetodyprzybliżone
Dużazłożonośćobliczeniowaproblemukolorowaniagrafówwymuszako-
niecznośćstosowaniaheurystycznychmetodprzybliżonychwceluznale-
zieniasuboptymalnychrozwiązańwczasiewielomianowym.Dooceny
efektywnościmetodyprzybliżonejmożnapodaćprzynajmniejkilkaróż-
nychkryteriów,oczympisaliśmywpoprzednimpunkcie.
DlagrafuGipewnejustalonejkolejnościwierzchołkówK=(υ1,
υ2,
...,υn)kolorowaniemzachłannymbędziemyokreślaćnastępującą
proceduręprzydziałukolorów:
algorytmKolorujZachłannie(G,K);
begin
