Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
PRZEDMOWAREDAKTORANAUKOWEGO
xiii
o5barwach.Potymwydarzeniuzainteresowaniedowodemtwierdzenia
o4barwachodżyłozezdwojonąsiłą.WpierwszejpołowieXXwieku
powstałowielepracnatematkolorowaniagrafów,gdyżichautorzysą-
dzili,żepomogąonewdowodzietwierdzeniao4barwach.Naprzykład,
sukcesywniepodnoszonoliczbępaństwnamapie,którenapewnodają
siępokolorować4barwamiz25w1922rokudo96w1971roku.
Przełomnastąpiłdopierowepocekomputerowej,gdyK.AppeliW.Ha-
ken[1]opublikowalipełnydowódtwierdzeniao4barwachdladowolnej
liczbypaństwnamapie.Dowódtenbyłwistotnysposóbwspomaganywie-
logodzinnymiobliczeniamikomputerowymi,gdyżwymagałsprawdzenia
prawie2000konfiguracjigrafowych.Zuwaginajegodługość(kilkaset
stron)iwykorzystaniekomputerawokółdowodupowstałapewnakontro-
wersja.„Dlakogoudowadniamytwierdzenia,dlaludziczydlakompute-
rów?”—pytalimatematycy-formaliści.Obecnieciąglepojawiająsięnowe
dowodytegotwierdzenia(np.[10]),leczwszystkieonewymagająużycia
komputera.Wogóleuważasię,żetwierdzenieo4barwach—obokwiel-
kiegotwierdzeniaFermata—należydotychproblemówmatematycznych,
któreniemają„krótkich”dowodów.
Zagadnieniekolorowaniamapjestrównoważnezadaniukolorowania
wierzchołkówgrafówplanarnych.Alewgrafiesątakżekrawędzie,któ-
remożnakolorować.Problemkolorowaniakrawędzitak,abywszystkie
krawędziestykającesięwdowolnymwierzchołkuotrzymałyróżnebar-
wy,narodziłsięw1880roku.Pierwsząpracęnatentematopublikował
P.G.Tait[11].Wartykuletymiwnastępnychpokazał,żeproblem4
barwjestrównoważnyproblemowi3-kolorowaniakrawędzidowolnejma-
pykubicznej.W1916rokuD.K¨
onig[7]udowodnił,żenajmniejszaliczba
kolorówwtakimpokolorowaniugrafudwudzielnegojestrównastopnio-
wigrafu.InnymważnymwynikiembyłotwierdzenieV.G.Vizinga[12]
oindeksiechromatycznymmultigrafów.Wartopodkreślić,żekolorowa-
niekrawędzigrafujestrównoważnekolorowaniuwierzchołkówjegografu
krawędziowego.
Modelekolorowania
Należywtymmiejscuzauważyć,żenapotrzebywieluzagadnień,których
niemożnabezpośredniosprowadzićdoklasycznegokolorowaniawierz-
chołkówczykrawędzi,tworzysiębardziejogólne,nieklasycznemodele
kolorowania.Kolorowaniegrafówmożewogólnościobejmowaćprzypi-
sywaniekolorówelementomzezbiorukrawędzi,wierzchołków,ściangra-
fupłaskiegolubróżnychkombinacjipowyższychobiektówjednocześnie.
