Problém čtyř barev

Šimon Žáček, 1. B

PROBLÉM ČTYŘ (PĚTI) BAREV

Jedná se o jeden z nejznámějších matematických problémů z teorie grafů, který byl vyřešen ve 2. polovině 20. století. Pojednává o tom, že k obarvení libovolné mapy tak, aby žádné dvě sousední země neměly stejnou barvu, stačí čtyři barvy. Za sousední země jsou považovány ty, které mají společný úsek hraniční čáry, nikoliv jeden bod. Zatím se nikomu nepodařilo tuto větu vyvrátit.

Obrázek 1.

Mapa světa obarvená 4 barvami (pro státy + 1 pro oceány).

Historie

Za historicky prvního člověka, který se tímto problémem zabýval, byl považován německý matematik August Ferdinand Möbius, který položil základy problému na jedné z přednášek roku 1840. V této době matematikové se samozřejmostí dokázali, že pět barev k obarvení každé mapy zaručeně stačí, ovšem nikdo si nelámal hlavu s tím, zda lze obarvit mapu i menším počtem barev.

Druhá zmínka pochází z Anglie, kde roku 1852 student Frederic Guthrie zjistil, že mapu hrabství v Anglii lze obarvit čtyřmi různými barvami tak, že žádné dvoje sousední hrabství nebyly stejně zbarvené. Tento objev mu zaslal jeho bratr, Francis, který žádný zájem o matematiku nejevil a objev udělal náhodou z čiré nudy, kdy si v novinách vybarvoval právě onu mapu.

Obrázek 2.

Mapa hrabství v Anglii obarvená 4 barvami.

Na základě tohoto objevu byla položena zásadní otázka, která nedala mnoha matematikům několik let spát: Jakým nejmenším počtem barev lze takto obarvit libovolnou mapu? Významný americký matematik zabývající se logikou a množinami C. S. Peirce se pokusil o odpověď na tuto otázku a zároveň důkaz se čtyřmi barvami, a pak o něm přenášel na Harwardu v roce 1860. Tento důkaz však nikdy nebyl publikován, a tak se matematici domnívají o jeho nesprávnosti.

Od roku 1878 se začal dostávat tento problém do povědomí širší veřejnosti poté, co byl referován na zasedání Londýnské matematické společnosti. V roce 1879 byl vydán v prestižním časopise American Journal of Mathematics důkaz o potvrzení hypotézy 4 barev od A. B. Kempeho. Tento důkaz byl shledán v roce 1890 za nesprávný a Percy J. Heawood jeho úvahu upravil tak, že obarvil jeho „mapu“ pěti barvami a tím potvrdil hypotézu 5 barev, bohužel zatím nikoli čtyř.

Obrázek 3.

Graf, přebarvený Percym Heawoodem v podání pěti barev.

A dlouhou dobu tedy nadále převládala právě hypotéza 5 barev a hypotéza 4 barev se snažila být vyvrácena, popřípadě docházelo k dalším omylným důkazům. Malý krok byl udělán, když se začala zkoumat hypotéza 4 barev pro větší a složitější mapy, neboť bylo jasné, že menší mapy mohly být obarveny čtyřmi barvami se zachováním oné podmínky. Roku 1922 P. Franklin dokázal, že tato hypotéza platí pro mapy s méně než 24 státy. Počet států na mapě se v průběhu dalších let začal zvyšovat, když každý matematik zkoumal stále větší a větší objekt rozdělený na nějaké správní celky. Později se strhl doslova souboj o to, kdo navýší již daný počet států na mapách, pro které platí teorém 4 barev. Mezi zapálené rivaly patřil i učitel francouzské literatury J. Mayer, který navýšil počet států až na úctyhodné číslo 96 roku 1974. Ovšem ještě nevěděl ani on ani nikdo jiný, že za 2 roky už se nebude moci v tomto oboru zápasit.