Problém čtyř barev

Z Wikipedie, otevřené encyklopedie

Politická mapa obarvená čtyřmi barvami

Jako problém čtyř barev se označuje 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.)

[editovat] 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).