Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
xii
PRZEDMOWAREDAKTORANAUKOWEGO
krycia,szeregowaniezadań,programowaniematematyczne,teorialiczb,
teoriaautomatów,lingwistykaiwieleinnych.Jednymzdziałówteorii
grafówjestkolorowaniegrafów,będącegłównymtematemtejksiążki.
Kolorowaniegrafów
Kolorowaniegrafówjestjednymznajstarszychinajbardziejznanychpro-
blemówteoriografowych,którydodziśbadasięianalizuje.Statystyki
internetowepokazują,żejesttocentralnezagadnieniewzbiorzekilku-
setklasycznychproblemówkombinatorycznych[2].Powodówtejsytuacji
możnaupatrywaćzjednejstronywprostociesformułowaniaipozornej
oczywistościproblemu.Zdrugiejstronyzadziwiającowielezagadnień,
zarównoczystoakademickich,jakiwynikającychzpraktycznychimple-
mentacji,dajesięsprowadzićdoszerokopojętegokolorowaniagrafów.
Taksiędziejezawszewtedy,gdyspotykamysięzzadaniempodziałuzbio-
ru,zawierającegowewnętrznekonfliktymiędzyelementami,napodzbiory
bezkonfliktowe.Niestety,takiemurozwiązaniuwieluznanychzagadnień
technicznychiekonomicznychstajenaprzeszkodziedużazłożonośćpro-
blemukolorowaniagrafów.Naprzykład,najprostszezadanieznalezienia
liczbychromatycznej,czyliwyznaczenieminimalnejliczbykolorów,któ-
rymimożnapokolorowaćwierzchołkigrafutak,abysąsiedziotrzymali
różnekolory,jestproblememNP-trudnym[3].Znaczyto,żeniesąznane
efektywnealgorytmypozwalającerozwiązaćtenproblemwczasiewie-
lomianowym,acozatymidzie,niejestmożliweznalezieniedokładnego
rozwiązaniawrozsądnymczasienawetdlagrafurozpiętegonakilkudzie-
sięciuwierzchołkach.Nietrzebauzasadniać,żewpraktycznychzastoso-
waniachtakirządgrafubywazregułyabsolutnieniewystarczający.
Ryshistorycznykolorowania
Problemkolorowaniagrafównarodziłsięw1852roku,kiedytoA.deMor-
gannapisałlistdoswegoprzyjacielaW.R.Hamiltonazwiadomością,że
jedenzjegostudentówzaobserwował,iżdopomalowaniamapyhrabstw
wAngliipotrzebajedynie4kolorów.Pierwszy„dowód”twierdzeniaoko-
lorowalnościdowolnejmapynapłaszczyźnieprzyużyciu4barwpojawił
sięw1879roku[6].Odtejchwiliświatnaukiuznał,żeproblem4barw
zostałrozwiązany.Cowięcej,jegoautora—A.B.Kempego—uho-
norowanowielomazaszczytami.Jednak,w1890rokuP.J.Heawood[4]
stwierdził,żeznalazłbłądwdowodzieKempego—błądtakpoważny,
żeniedałosięgousunąć.Ponadtopodałpoprawnydowódtwierdzenia