Problém 4 barev

22. listopad 2008 | 06.00 |
› 

4 barvy

Tento problém pochází z matematické teorie grafů.  Prvním, kdo byl s tímto problémem spojován, je německý matematik a zakladatel topologie August Ferdinand Möbius. Na své přednášce z roku 1840 uvádí teoretické základy problému. O 12 let později se anglický student Frederic Guthrie pokoušel vybarvit mapu Anglie rozdělenou na hrabství. Chtěl ji vybarvit tak, aby každá oblast měla jinou barvu než oblast sousední. Jaký je nejmenší počet barev, který by na to stačil, pokud se sousední oblasti nikdy nestýkají pouze v bodě?

Po mnoha pokusech a omylech napsal svému mladšímu bratrovi a zeptal se, zda každá mapa nakreslená v rovině může být vybarvena 4 (či méně) barvami tak, aby žádné dvě oblasti se společnou hranicí neměly společnou barvu. Jeho bratr problém nevyřešil a tak jej postoupil matematikům a tak se až v roce 1878 stal tento problém všeobecně známým. Matematikové se snažili toto tvrzení dokázat, ale bylo publikováno mnoho vadných důkazů a jejich následných kritik.

V teorii grafů je tento úkol formulován jako obarvení vrcholů planárního grafu tak, aby žádné dva vrcholy spojené hranou neměly stejnou barvu. Úloha s mapou se na tuto variantu transponuje tak, že každému státu se přiřadí jeden vrchol (hlavní město státu) a čárou se spojí ty vrcholy, jejichž státy mají společnou hranici.

Percy Heawood tento problém zevšeobecnil a zeptal se, zda by bylo možné vybarvení mapy tímto způsobem nakreslené na jiných typech plochy (kouli, pneumatice – anuloidu...). Pak se dlouhou dobu nedělo nic až v roce 1968 byl tento problém vyřešen pro neobvyklé tvary – anuloid a Kleinovu láhev, kde stačí 7 barev. Nicméně pro mapu na rovině či kouli se důkaz stále nedařil.

V roce 1970 Wolfgang Haken z univerzity v Illinois zredukoval problém na seznam všech možných typů map, v nichž by hypotéza o 4 barvách mohla selhat. Tento seznam je tak rozsáhlý, že ho nelze projít případ za případem jen pomocí tužky, papíru a čistého přemýšlení. Vypadalo to, že k prozkoumání všech možností bude potřeba více než 100 let. Pak ale Haken začal navrhovat počítačový program, který by tento dlouhý seznam možností prošel v rozumném čase. Program sám byl spuštěn mezi lednem a červnem 1976 a provedl kontrolu všech zbývajících možných map, pro něž by čtyři barvy nemusely stačit. Žádná z nich nevyžadovala 5 barev.

Nikdy předtím nebyl klasický problém matematiky vyřešen jinak než lidským myšlením, proto se brzy na to začali ozývat matematikové a filozofové s otázkami, zda se tento důkaz opravdu počítá. Co když počítačový program obsahoval programátorskou chybu aneprošel všechny možnosti? Nicméně důkaz samotný je tak obsáhlý, než aby mohl být zkontrolován ručně. Čekalo se, že hypotéza o 4 barvách je pravdivá. K tomu, aby se prokázalo, že je nepravdivá, by musel být ukázán protipříklad v podobě určité mapy vyžadující více než 4 barvy. Jinou možností vyvrácení hypotézy by byla úvaha, že její pravdivost by vedla k logickému sporu. Můžeme si tedy být jisti, že matematikové budou pokračovat v hledání tohoto výsledku, jenž by nevyužíval počítače.

Zpět na hlavní stranu blogu

Hodnocení

1 · 2 · 3 · 4 · 5
známka: 2.43 (7x)
známkování jako ve škole: 1 = nejlepší, 5 = nejhorší

Komentáře

RE: Problém 4 barev fanatiČka 04. 05. 2011 - 15:21
RE(2x): Problém 4 barev fyzmatik 04. 05. 2011 - 17:52