Věta o čtyřech barvách

Věta o čtyřech barvách říká, že jakákoli mapa umístěná na rovině nebo na kouli může být obarvena nejvýše čtyřmi různými barvami (barvami), takže libovolné dvě oblasti se společným hraničním segmentem mají různou barvu. Současně musí být oblasti propojeny [1] (to znamená, že oblast nemůže sestávat ze dvou nebo více samostatných „kusů“) a hranice musí být nebodová (v jednom bodě tolik oblastí, kolik chcete se mohou dotýkat svými rohy, včetně těch natřených stejnou barvou).

V roce 1852 si Francis Guthrie , při sestavování mapy hrabství Anglie, všiml, že pro takový účel stačí čtyři barvy. Jeho bratr Frederick oznámil toto pozorování slavnému matematikovi Augustu de Morganovi , který to řekl matematické komunitě. Přesnou formulaci hypotézy publikoval Arthur Cayley (1878) [2] . Dokázat větu trvalo dlouho. Bylo učiněno mnoho pokusů dokázat i vyvrátit a tento problém byl nazýván problémem čtyř barev [3] .

U jednoduchých map stačí tři barvy a čtvrtá barva je nutná například tehdy, když je jedna oblast obklopená lichým počtem dalších, které se navzájem dotýkají a tvoří cyklus. Věta o pěti barvách , která říká, že pět barev stačí, měla krátký, jednoduchý důkaz a byla prokázána na konci 19. století, ale důkaz věty pro případ čtyř barev narážel na značné potíže.

Čtyřbarevný teorém byl prokázán v roce 1976 Kenneth Appel a Wolfgang Haken na University of Illinois . Byla to první velká matematická věta, kterou dokázal počítač. Prvním krokem důkazu bylo prokázání existence určité sady karet z roku 1936, z nichž žádná nemohla obsahovat menší kartu, která by teorém vyvracela. Autoři pomocí speciálního počítačového programu prokázali tuto vlastnost u každé z karet z roku 1936. Důkaz této skutečnosti zabral stovky stran. Poté Appel a Haken došli k závěru, že neexistuje nejmenší protipříklad k teorému, protože jinak by musel obsahovat jednu z těchto karet z roku 1936, což neobsahuje. Tento rozpor říká, že neexistuje žádný protipříklad.

Zpočátku nebyl důkaz akceptován všemi matematiky, protože jej nelze ručně ověřit. Později získal širší přijetí, i když někteří o něm dlouho pochybovali. Aby se rozptýlily zbývající pochybnosti, v roce 1997 Robertson, Sanders, Seymour a Thomas publikovali jednodušší důkaz s použitím podobných myšlenek, ale stále prováděný pomocí počítače. Navíc v roce 2005 provedl důkaz Georges Gonteer pomocí specializovaného softwaru ( Coq v7.3.1) [4] .

Ekvivalentní formulace

V teorii grafů má tvrzení teorému o čtyřech barvách následující formulace:

Je známo mnohem více ekvivalentních formulací [5] .

Historické pokusy o důkaz

Nejznámější důkazní pokusy jsou:

Variace a zobecnění

Jiné povrchy

Podobné problémy pro ostatní povrchy ( torus , Kleinova láhev atd.) se ukázaly být mnohem jednodušší. Pro všechny uzavřené povrchy, s výjimkou koule (a její ekvivalentní roviny a válce) a Kleinovy ​​láhve , lze požadovaný počet barev vypočítat z jejich rodu pomocí následujícího vzorce, který v roce 1890 navrhl Percy John Heawood : [9]

Horní mez se získá celkem jednoduše, dokázal to sám Heawood (pro kouli vzorec dává správnou odpověď - 4, ale Heawoodův důkaz na ni neplatí). Spodní je dokázáno vložením celého grafu do odpovídajícího povrchu; důkaz postavila v letech 1952-1968 skupina matematiků, poslední krok udělali Gerhard Ringel a John Youngs . [10] [11] [12]

Pro Möbiův pás (stejně jako pro projektivní rovinu ) je zapotřebí 6 barev. Pro jednostranné povrchy rodu , [11]

U Kleinovy ​​láhve (rod ) je číslo 6 (a ne 7, jak podle vzorce) - to ukázal P. Franklin v roce 1934. [13]

Mapa ostrova

Z věty o čtyřech barvách vyplývá, že mapu ostrova, na kterém má každá země přístup k moři, lze vybarvit 3 barvami. Toto tvrzení má však také elementární důkaz.

Problém impéria

Podobný problém pro mapy s koloniálními říšemi (tedy se zeměmi skládajícími se z několika samostatných „kusů“ na mapě, jejichž počet je m ), zvažoval Percy John Heawood . Když odpověď . Horní mez se získá celkem jednoduše, dokázal to sám Heawood. Spodní je dokázáno vložením celého grafu do odpovídajícího povrchu; důkazem jsou Gerhard Ringel a Brad Jackson. [čtrnáct]

Varianta problému o říších s koloniemi na jiných planetách zůstává otevřená. Pokud má například každá země na Zemi kolonii na Měsíci, jsou známy pouze odhady

Vyšší rozměry

Ve vyšších dimenzích neexistuje žádné rozumné zobecnění problému, protože je snadné přijít s trojrozměrnou mapou s libovolným počtem oblastí, které se všechny navzájem dotýkají. .

Hra "čtyř barev"

Stephen Barr navrhl papírovou logickou hru pro dva hráče s názvem „Four Colors“. Slovy Martina Gardnera  : „Neznám lepší způsob, jak porozumět obtížím spojeným s řešením čtyřbarevného problému, než pouhým hraním této kuriózní hry“ [15] .

Tato hra vyžaduje čtyři barevné tužky. První hráč zahájí hru kreslením libovolné prázdné oblasti. Druhý hráč jej vybarví kteroukoli ze čtyř barev a následně si nakreslí svou prázdnou oblast. První hráč vybarví oblast druhého hráče a přidá novou oblast a tak dále - každý hráč vybarví oblast soupeře a přidá svou vlastní. V tomto případě by oblasti, které mají společnou hranici, měly být namalovány v různých barvách. Ten, kdo na svém tahu bude nucen vzít pátou barvu, prohrává.

V této hře není ztráta jednoho z hráčů vůbec důkazem nesprávnosti věty (čtyři barvy nestačily), ale pouze ilustrací toho, že podmínky hry a věty jsou velmi odlišné. . Chcete-li zkontrolovat správnost teorému pro mapu získanou ve hře, musíte zkontrolovat konektivitu nakreslených oblastí a po odstranění barev z ní zjistit, zda je možné vystačit pouze se čtyřmi barvami pro malování výsledného mapa (teorém říká, že je to možné).

Existují také následující varianty hry:

  1. Mapa je předem náhodně rozdělena do oblastí různých velikostí. Při každém tahu se mění hráč, který maluje oblast, a v přísném pořadí se mění i barva. Každý hráč tedy vybarví kartu pouze dvěma barvami. Hráč zmešká tah, pokud nemůže vybarvit oblast tak, aby byla barva sousedních oblastí odlišná. Hra končí, když už žádný z hráčů nemůže provést žádné další tahy. Vítězí ten, kdo má větší celkovou plochu zastíněných ploch.
  2. Čtverec se stranami různě barevnými v jedné ze čtyř barev je rozdělen na několik čtverců (obvykle 4 × 4). První tah maluje přes pole sousedící se stranou, v dalších tazích můžete malovat přes pole, které sousedí s jedním z vyplněných polí. Čtverec nelze přebarvit barvami, kterými je přebarveno jedno z polí sousedících s ním nebo strana sousedící se čtvercem. Vyhrává hráč, který provede poslední tah.

V kultuře

Viz také

Poznámky

  1. ↑ Frank Harari. Four Color Conjecture // Graph Theory = Graph Theory. - M .: Mir , 1973. - S. 17-18.
  2. ↑ Samokhin A.V. Problém čtyř barev: nedokončená historie důkazu  // Sorovsky vzdělávací časopis. - 2000. - T. 6 , č. 7 .
  3. ↑ 1 2 3 J. J. O'Connor, E. F. Robertson. Věta o čtyřech barvách . MacTutor historie archivu matematiky . School of Mathematics and Statistics, University of St Andrews, Skotsko (září 1996).
  4. ↑ Georges Gonthier. Počítačově ověřený důkaz teorému čtyř barev  . Microsoft Research Cambridge (2005). Archivováno z originálu 5. června 2022.
  5. ↑ 1 2 Shor N. Z. , Donets G. A. K problému čtyř barev // Matematika dnes / ed. prof. A. Ya. Dorogovtseva  - Kyjev, škola Vishcha, 1982. - Náklad 3000 výtisků. — c. 33-53
  6. ↑ Lakeev A.V. Základy teorie obyčejných grafů. - Irkutsk: Nakladatelství IGU, 2014. - S. 7. - 92 s.
  7. ↑ A.B. Kempe. O geografickém problému čtyř barev  (anglicky)  // Amer. J Math. . - 1879. - Sv. 2 . - S. 193-200 .
  8. ↑ P.G. Tait. Poznámka k větě o geometrii polohy   // Trans . Royi. soc. Edinburgh . - 1880. - Sv. 29 . - S. 657-660 .
  9. ↑ Percy John Heawood. Map-Color Theorem  (anglicky)  // Quarterly Journal of Mathematics, Oxford. - 1890. - Sv. 24 . - str. 332-338 .
  10. ↑ G. Ringel, JWT Youngs. Řešení problému zbarvení mapy Heawood   // Proc . Nat. Akad. sci. USA. - 1968. - Sv. 60 , iss. 2 . - str. 438-445 . - doi : 10.1073/pnas.60.2.438 . — PMID 16591648 .
  11. ↑ 1 2 Ringel G. Map coloring theorem / Z angličtiny přeložil V. B. Alekseev. — M .: Mir, 1977. — 256 s.
  12. ↑ Boltyansky, 1982 , s. 77.
  13. ↑ P. Franklin. Šestibarevný problém  //  J. Math. Phys. - 1934. - Sv. 13 . - str. 363-369 .
  14. ↑ Jackson, Brad; Ringel, Gerhard. Problém Heawoodova impéria  //  J. Combin. Teorie Ser. B. - 1985. - Sv. 38 , č. 2 . - S. 168-178 .
  15. ↑ Martin Gardner. Problém čtyř barev // Matematické hádanky a odbočky = Matematické hádanky a odbočky: [přel. z  angličtiny. ]. - 2. vyd. - M  .: Mir , 1999. - S. 389-390. — 447 s. — ISBN 5-03-003340-8 .
  16. ↑ Martin Gardner. Ostrov pěti barev . N.Y .: Fantasia Mathematica , 1958.

Literatura

  Přejděte na položku Wikidata  Slovníky a encyklopedie