Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
xiv
PRZEDMOWAREDAKTORANAUKOWEGO
Ponadto,dlaróżnychmodelikolorowaniaobowiązująrozmaitereguły,de-
cydująceolegalnościczyoptymalnościrozwiązań.Nieklasycznemodele
mogąwprowadzaćdodatkoweograniczenianaużywaniekolorów,zezwa-
laćnaprzypisywaniewięcejniżjednegokoloru,zezwalaćnadzielenie
i„zawijanie”kolorówitd.
Ogólnie,wliteraturzeprzedmioturozważasiękilkadziesiątróżnych
modelikolorowaniagrafów[5].Jednakżetylkokilkanaścieznichmazna-
czeniepraktyczne.Spośródmodelinieklasycznych,któresąwykorzysty-
wanepraktycznie,należywymienić:kolorowanielistowe,sumacyjne,spra-
wiedliwe,cząstkowe,uporządkowane,harmoniczne,kontrastowe,zwarte,
obserwowalne,cyrkularne,silneiścieżkowe.Większośćznichdotyczy
zarównokolorowaniawierzchołków,jakikrawędzi,leczniektóresąokre-
ślonewyłączniedlawierzchołków(np.harmoniczne,obserwowalne)lub
krawędzi(np.zwarte).
Wniniejszejksiążcerozważasięszczegółowowiększośćużytecznych
modelikolorowaniagrafów.
Sątowkolejnościnastępującekolorowania:
•
klasyczne,
•
sprawiedliwe,
•
sumacyjne,
•
kontrastowe,
•
harmoniczne,
•
cyrkularne,
•
zwarte,
•
ścieżkowe,
•
listowe.
Poszczególnerozdziały,poświęconewymienionymmodelom,sąwdu-
żymstopniuautonomiczneimogąbyćczytaneniezależnieodinnychroz-
działów.Wkażdymznichakcentpołożononazagadnieniaalgorytmiczne,
tj.nakonstrukcjęwielomianowychalgorytmówkolorowania.Sątoalgo-
rytmydokładne,gdydanypodproblemzezwalanatakierozwiązanie,lub
przybliżone—wprzypadkuogólnym.
Powyższywybórmodeliniejestprzypadkowy.Uwzględnionotubo-
wiemzakrespraktycznychzastosowań,któresięgajątakodległychdzie-
dzin,jak:szeregowaniezadań,telekomunikacjaoptyczna,technologiacien-
kowarstwowa,telefoniakomórkowa,radionawigacjalotniczaiorganizacja
produkcji.Ogólnie,liczbaudokumentowanychzastosowańróżnychmodeli
kolorowaniagrafów,zarównowierzchołkówjakikrawędzi,sięgakilku-
dziesięciu[8,9].
