Problém čtyř barev

Problém čtyř barev či také věta o čtyřech barvách je (již kladně vyřešený) problém z teorie grafů, který zní: „Stačí čtyři barvy na obarvení libovolné politické mapy tak, aby žádné dva sousedící státy nebyly obarveny stejnou barvou?“ (Za sousední státy jsou považovány takové, že mají společnou hraniční čáru tj. nesousedí spolu jen v jednom bodě.) Obecněji se lze tázat na minimální potřebný počet barev, lze však poměrně snadno dokázat, že pět barev postačuje. Oproti tomu tvrzení, že čtyři barvy stačí, dlouhou dobu odolávalo všem pokusům o důkaz, nikdo však také nebyl schopen nalézt mapu, která by ho vyvrátila.

Větu dokázali až roku 1976 američtí matematici Kenneth Appel a Wolfgang Haken tím, že pomocí počítačového programu vymodelovali 1936 možných konfigurací, dokázali, že tyto konfigurace pokrývají všechny možnosti, a u každé z nich ukázali, že pro její obarvení čtyři barvy stačí (k tomu potřeboval 1200 hodin procesorového času). Tento důkaz však velká část matematiků odmítá akceptovat, protože ho žádný matematik není schopen přímo zkontrolovat. (Od té doby byl důkaz mnohokrát nezávisle zopakován a zjednodušen dalšími matematiky pomocí jiných programů, ale „hezký“ důkaz vhodný pro člověka nalezen nebyl.)

Formulace v teorii grafů

Formálně se tento problém v teorii grafů podává tak, že cílem je obarvení vrcholů planárního grafu tak, aby žádné dva vrcholy spojené hranou neměly stejnou barvu. Formulace s mapou se na tuto verzi převede tak, že každému státu se přiřadí jeden vrchol (např. hlavní město) a hranou se spojí ty vrcholy, jejichž státy mají společnou hranici.

Problém lze zobecnit i na grafy na jiném povrchu než rovině, např. mapa zobrazená na kouli má v tomto ohledu stejné vlastnosti jako rovinná mapa. U uzavřených povrchů s genem g udává počet postačujících barev (tzv. chromatické číslo grafu) rovnost

\gamma (g)=\left\lfloor {\frac {7+{\sqrt {48g+1}}}{2}}\right\rfloor

,

kde vnější závorky označují zaokrouhlení na nejbližší menší celé číslo. Tento vzorec se označuje jako Heawoodova hypotéza. Fakt, že tento počet barev je nejnižší možný, dokázali pro všechny povrchy s výjimkou Kleinovy láhve a koule (a roviny) roku 1968 Gerhard Ringel a J. T. W. Youngs. Po důkazu problému čtyř barev zůstává jedinou výjimkou Kleinova láhev, která má genus 1, ale vyžaduje 6 barev (což dokazuje tzv. Franklinův graf).

Populární aplikace tohoto matematického problému na politické mapy vyžaduje několik upřesnění: Regiony, které se stýkají v jediném bodě, nejsou považovány za sousední (na mapě ve tvaru kruhu rozděleného na výseče se takto může stýkat libovolné množství oblastí, takže by taková mapa jinak vyžadovala shora neomezené množství barev). Zvažované regiony mohou obsahovat enklávy (regiony zcela obklopené jedním jiným regionem), ale nesmějí obsahovat exklávy: dva oddělené regiony jsou považovány za dva různé regiony a nemůže být vyžadováno, aby byly vybarveny stejnou barvou (pokud by to vyžadováno bylo, šlo by to reprezentovat propojením těchto dvou oblastí mimo zvažovanou rovinu mapy; lze ukázat, že tím by se problém změnil z problému v rovině na problém na toru (s genem 1), kde je vyžadováno až sedm barev).

Historie

První zmínka o problému pochází od A. F. Möbiuse, který o něm pojednává ve své přednášce v roce 1840. Druhá zmínka je datována do roku 1852, A. de Morgan píše W. R. Hamiltonovi o svém studentovi, který zjistil, že politickou mapu Anglie je možné zbarvit čtyřmi barvami. Zmiňovaný student byl Frederic Guthrie. O témže problému referoval A. Cayley v roce 1878 na zasedání Londýnské matematické společnosti. Významný americký matematik v oblasti teorie množin a logiky C. S. Peirce se pokusil o důkaz hypotézy čtyř barev a přednášel o něm na Harvardu v roce 1860. Protože C. S. Peirce svoji práci nepublikoval, má se za to, že důkaz zřejmě nebyl správný, protože se nedochovalo ani jeho autentické znění.

V roce 1879 uveřejnil svůj nezdařený pokus hypotézy 4 barev A. B. Kempe v časopise American Journal of Mathematics. V roce 1890 totiž upozornil P. J. Heawood, že se Kempe dopustil chyby. Nicméně Heawood Kempeho úvahu modifikoval a upravil tak, že se mu podařilo dokázat, že 5 barev spolehlivě stačí k zabarvení každé mapy. Toto tvrzení, kterému se též říká hypotéza pěti barev, bylo na několik desetiletí jediným výsledkem s definitivní platností až do roku 1976, kdy se podařilo hypotézu o 4 barvách dokázat.

Když se důkaz tohoto tvrzení (4 barvy) nedařil, snažili se mnozí zájemci o řešení sestrojit protipříklady, které by domněnku vyvrátily. Při zkoumání malých map 4 barvy postačovaly. Ukazovalo se proto, že půjde o podstatně složitější mapy. Průkopníkem v uvedené oblasti byl P. Franklin, který v roce 1922 dokázal, že pro mapy s méně než 24 státy teorém funguje. Na 28 zvýšil počet států C. N. Reynolds v létech 1927-27. Na 32 to byl opět Franklin v roce 1938. Na 36 C. E. Win v roce 1940. Na 40 potom O. Ore s G. J. Stemplem v roce 1970, vzápětí G. A. Doněc a Stromquist na 45.

Zajímavou postavou v popisovaném „zápolení“ je bezesporu J. Mayer, který nebyl matematik, nýbrž profesor francouzské literatury na univerzitě Montpellier ve Francii. Začátkem 70. let Mayer zvýšil hranici na 48 a Stromquist odpovídá hranicí 52. Krátce nato dosáhl Mayer skoro neuvěřitelných hodnot 72 a 96. To bylo v roce 1974, v době konání II. československého sympózia o teorii grafů, kde se o řešení problému živě diskutovalo, ale ještě se nevědělo, že rozuzlení „záhady“ je blízko.

Konečně v roce 1976 K. Appel a W. Haken z univerzity v Illinois oznámili, že problém vyřešili. Řešení si vyžádalo 1200 hodin strojového času. Plný důkaz má 56 stran textu a 114 stran obrázků (30 na každé straně).

Literatura

ŠIŠMA, Pavel. Problém čtyř barev. In: BEČVÁŘ, Jindřich; FUCHS, Eduard. Historie matematiky II.. Praha: Prometheus, 1997. Dostupné online. ISBN 80-7196-046-2. S. 169–180.
ŠIŠMA, Pavel. Teorie grafů 1736-1963. Brno: Prometheus, 1997. ISBN 80-7196-065-9.

Externí odkazy

Obrázky, zvuky či videa k tématu problém čtyř barev na Wikimedia Commons
Z historie matematiky a fyziky (3)
Problém čtyř barev v encyklopedii MathWorld (anglicky)