Problém čtyř barev

Ano, roku 1976 se udělala pomyslná tečka v tomto problému, neboť dvojice matematiků Kenneth Appel a Wolfgang Hakel z univerzity v Illinois přinesli na svět kompletní důkaz hypotézy 4 barev. Dosáhli jej pomocí počítačového programu, v němž vymodelovali 1482 možných konfigurací, které pokrývají všechny možnosti mapy, která je obarvena čtyřmi čtyřmi barvami. Mimo jiné jim tento důkaz trval 1200 hodin procesorového času a má 56 stran textu + 114 stran s obrázky. Mnoho matematiků odmítlo tak náročně vyložený důkaz, navíc za pomocí počítače a některým z nich se podařil trochu zjednodušit. Sám Wolfgang Hakel pár let před důkazem vyhodnotil, že vyzkoušet platnost hypotézy 4 barev u všech složitějších map za pomocí tužky, papíru a lidského přemýšlení by trvalo bezesporu přes 100 let. Ovšem důkazu shrnutého v pár větách se u tohoto problému nikdy nepodařilo docílit.

Pro zajímavost, rok před důkazem hypotézy 4 barev si Martin Gardner udělal aprílový vtípek z tohoto problému tím, že v jednom časopisu zveřejnil neobarvenou mapu 110 regionů, u které tvrdil, že její obarvení vyžaduje pět barev a tím (falešně) vyvrátil později dokázaný teorém 4 barev. Každopádně, jak je vidět níže, i tuto mapu lze obarvit pouze čtyřmi barvami (čehož bylo docíleno algoritmicky pomocí Wolfram jazyka).

Obrázek 4.

Aprílový šprým Martina Gardnera vyobrazující falešný důkaz hypotézy čtyř barev.

Souvislost s teorií grafů

Tento problém se převádí do teorie grafů tak, že se jednotlivé státy převedou do vrcholů rovinného grafu s tím, že sousední státy se spojí hranami. Poté i touto cestou lze potvrdit, že obarvením grafu čtyřmi barvami žádné dva sousední vrcholy (tj. státy) nebudou mít stejnou barvu.

Obrázek 5.

Ukázka převedení mapy do grafu a následného „obarvení“.

Tento problém lze uplatnit i na jiné prostorové útvary, než je rovina. Mapu, která se zobrazí na kouli, lze taktéž jako rovinnou mapu obarvit čtyřmi barvami se zachováním oné podmínky.

Avšak jinak je to u dalších typů ploch, například u anuloidu (pneumatiky) či Keinovy láhve, u kterých bylo roku 1968 Percym Heawoodem dokázáno, že k obarvení bez společného sdílení hranic sousedních oblastí stačí 7 barev. Tato hypotéza tedy ještě předcházela vyřešení problému čtyř barev a došlo se v ní relativně dále.

U uzavřených povrchů byla vytvořena rovnice k výpočtu nejnižšího možného počtu barev k obarvení daného útvaru. Tato rovnice neplatí akorát pro rovinu, kouli a Kleinovu láhev.

Obrázek 6.

Ukázka složení anuloidu tak, aby žádné 2 z jeho 8 částí na povrchu neměly stejnou barvu.

Důkaz, že k obarvení mapy jsou potřeba nejméně 4 barvy

Jak už tu bylo napsáno, dokázat hypotézu čtyř barev by trvalo i desítky let. Z jejího důkazu je jasné, že mapy obarvené více barvami také budou onu větu splňovat. Avšak mnoha matematikům i laikům vrtá hlavou, zdali by nešlo libovolnou mapu obarvit menším počtem barev. Samozřejmě je jasné, že pro určitý počet oblastí nemusíme využít všech čtyř barev, ale když už se počet oblastí zvětší, je dobré si ověřit, pokud až budeme ten menší počet barev potřebovat. Ideálním příkladem jsou státy USA (vyplňovat se bude od středu - cca. Kansas).