pondělí 8. června 2020

Mapy a problém 4 barev

V knize Vesmírná galerie, J. D. Barrow (2011), mě zaujala malá kapitola týkající se tzv. Problému čtyř barev, nebo Věty o 4 barvách. Jde o to, co pozorovali již dávno kartografové, že libovolnou politickou mapu lze zakreslit jen s pomocí 4 barev tak, aby se nikdy nedotýkaly státy se stejnou barvou (viz. ilustrace z citované knihy Vesmírná galerie nebo práce P. Kováře - Úvod do teorie grafů, 2016). Od roku 1850 se důkazu věnují matematici, až nakonec roku 1976 podali kontroverzní důkaz této věty matematici z univerzity v Illinois (K. Appel, W. Haken).

 

 

Důkaz dvojice Appel-Haken byl zejména kontroverzní v tom, že byl podán ne obvyklým matematickým formátem věta a důkaz, který si lze přečíst, ale s pomocí počítačového programu. Důkaz byl postaven na modelu 1936 možných konfiguracích, kde pánové dokázali, že skutečně takto pokrývají všechny možnosti a že pro každou z nich skutečně stačí 4 barvy. Podívat se na tento důkaz zdá se není možnost pro širokou veřejnost, ať už co do faktické dostupnosti dat, map a programu, tak i z pohledu pravděpodobnosti, že důkaz pochopí i průměrný člověk. Ostatně, problém 4 barev i mnoho podobných problémů je obvykle převedeno do řeči Teorie grafů diskrétní matematiky, která popisuje množinu objektů (vrcholky grafu) a vztahy mezi nimi (hrany grafu). Jak je patrné z obrázků níže (Úvod do teorie grafů, P. Kovář, 2016), nejde o žádné grafy trendů zlepšení efektivity výroby ani o grafy funkcí:

 

 

Proto nabízím na dalších řádcích svůj jednoduchý pohled na problém aplikovatelný na všechny konfigurace, které si já umím představit a které jsou i hezky vyobrazené v knize Vesmírná galerie, J. D. Barrow (2011).

 

 

Rozhodně však nejde o matematický důkaz, ale třeba jednou tento model, který popisuje přechod z přímky (1D) na papír (2D), přijatelnější matematickou interpretaci problému 4 barev pomůže sestavit.

 

To, co člověk chápe jako odlišné oddělené barevné plochy je snadné představit si na obrázku čtverců zakreslených do přímky (obr. 1), kde se dotýkají každého čtverce jen jeden zleva a jeden zprava (strany b a d). Na rozlišení postačí dvě barvy, resp. ještě obvykle bílé pozadí (papír). Pokud se bavíme o mapách, tedy ploše papíru, a přímku, v které původně byly čtverce zakreslené, začnu ohýbat (obr. 2), bude role pozadí markantnější a strany c musí být odděleny třetí barvou, zelenou. Čím více obrázek ohýbám až do možných 180°, hrozí riziko spojení dvou modrých barev skrze strany d a b (obr. 3). K oddělení dvou modrých oblastí však nelze využít červenou, protože toto pole může snadno „expandovat“ (obr. 4) a tedy musím použít další, 4. barvu (hnědou).

 

  

 

Tedy

# zelená odděluje všechny barvy
# červená, která expandovala případně převzala roli pozadí, nemůže vykrýt oblast, která odděluje dvě modrá pole od sebe a proto

# roli oddělovače konfliktu modrých barev převezme 4. barva, hnědá

 

Pátá barva by byla v tomto dvourozměrném problému nadbytečná, i kdyby bylo v původním linearizovaném modelu mnoho čtverců (objektů). Zatímco na přímce potřebuji 2 barvy, na ploše potřebuji 4 barvy.

Kolik barev potřebuji v prostoru, resp. objemu?

V čem je slabina celé úvahy výše? Vadí, že jsem si jako model vybral právě čtverec?


Žádné komentáře:

Okomentovat