Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Rozdział1
KrzysztofManuszewski
Klasycznekolorowaniegrafów
Mimowykorzystywaniawpracachteoretycznychrozmaitychmodeliko-
lorowania,bardzoważny,bynierzecpodstawowy,dlawieluzastosowań
pozostajemodelklasyczny.NP-trudnośćproblemukolorowaniapowodu-
je,żewpraktycetrzebaposługiwaćsięmetodamiprzybliżonymi.Zko-
leimnogośćowychzastosowań,specyfikaproblemóworazróżnorodność
pojawiającychsiętamklasgrafówsprzyjająpowstawaniuciąglenowych
algorytmówprzybliżonych.Obszernyprzeglądtakichalgorytmówzawiera
np.praca[19].Możnapodaćprzynajmniejkilkanaściestosunkowopro-
stychmetod,zaliczanychdoklasycznychzewzględunaczaspowstania
czypowszechnośćzastosowańpraktycznych.Ponieważdoimplementacji
konkretnychrozwiązańprogramowychkoniecznyjestwybórjednejlub
kilkumetodkolorowania,niezbędnestająsiękryteriaocenyiwyborual-
gorytmówkolorowania.Bardzoważnymkryteriumocenyalgorytmujest
oczywiścieszybkośćdziałania,którąmożnaocenićszacujączłożoność
obliczeniowądanejmetody.Dlaalgorytmówprzybliżonychistotnymele-
mentemocenyjestfunkcjadobroci,określającajakdobre,czyraczejjak
złemogąbyćwynikiuzyskaneprzyużyciudanejmetody.Innymkryte-
rium,komplementarnymwobecfunkcjidobroci,jestanalizanajmniejszych
trudnychdokolorowaniagrafów.
