Intuitivní východiska konstrukce krátkého důkazu teorému o čtyřech barvách

Svého času mne kdovíproč zaujal problém čtyř barev. Od té doby, co jsem se s ním poprvé setkal, mne ledacos napadlo a to podstatné pro důkaz teorému o čtyřech barvách se snaží shrnout tato stať. Je ovšem ode mne vůbec troufalost, že ji píši, protože co do potřebné odbornosti jsem naprostý laik. Přesto mi to nedalo a pokusil jsem se vyslovit se aspoň tak, jak je to v mých silách, s nadějí, že třeba přece jen to k něčemu či někomu bude.

Teorém o čtyřech barvách lze zformulovat takto:

(T) K vybarvení všech polí libovolné politické mapy je potřeba nejvýše čtyř barev.

Ačkoliv teorém je dokázán (viz pozn. 1), chceme důkaz provést také, ovšem méně náročným způsobem, a to tak, že se pokusíme sestrojit útvar vynucující pátou barvu. Pokud dokážeme, že takový útvar sestrojit nelze, domníváme se, že to dokazuje platnost (T).

Pro analýzu úlohy používáme již vžitý aparát teorie grafů, v němž uzly zastupují mapová pole, hrany dotyky těchto polí a graf sám útvar složený z polí a dotyků, tedy mapu. Z důvodů, jež nerozvádíme, uvažujeme vždy pochopitelně rovinný graf, jehož hrany se neprotínají, přičemž dotyk polí nikdy není bodový, nýbrž vždy tvoří hranici dotyku spojitá množina bodů (čára). Budeme konstruovat grafy přiměřených vlastností, a hledat tak útvary o vlastnostech, jež jsme si vytkli.

Udělíme-li poli barvu z množiny barev MB = (1, 2, 3, 4, ...), kde po řadě jdoucí přirozená čísla n označují konkrétní vzájemně různé barvy, v grafu to zapíšeme příslušným číslem n u příslušného uzlu.

V úvodu je vhodné zavést některé pojmy.

Minimální udílení barev: Útvaru U udílíme barvy z množiny barev MB = (1, 2, 3, 4, ...) tak, aby největší n bylo co nejmenší. Najdeme-li takové udílení barev, řekneme, že útvar U si vynucuje n barev a jeho maximální počet barev nutných k vybarvení MAX (U) = n.

Vynucování n + 1. barvy: Vedeme-li pro útvar U minimální udílení barev za předpokladu MAX (U) = n a při každém udílení dojdeme k poli, jemuž nelze udělit barvu z množiny barev MB = (1, ..., n ), pak řekneme, že útvar U si vynucuje n + 1. barvu a že MAX (U) je větší než n. Vynucuje-li si útvar U jen n + 1. barvu, pak MAX (U) = n + 1.

V čem tkví podstata vynucování n barev? V tom, že při každém udílení barev z množiny barev MB = (1, ..., n - 1) určitá struktura polí navodí situaci, v níž se některé pole A dotýká alespoň (n - 1) různých polí, z nichž každé nabylo jinou barvu. Potom má pole A nutně n-tou barvu.

Na této úvaze lze založit postup, kterým se budeme snažit zkonstruovat útvar vynucující n barev.

Východiska konstrukce útvaru U s MAX (U) = n, čili jak sestrojíme útvar vynucující n barev:

n = 1

1 barvu vynucuje pole, jehož se nic nedotýká.

n = 2

Polem bude vynucována 2. barva, pokud se bude dotýkat jiného pole.

n = 3

Polem bude vynucována 3. barva, pokud se bude zároveň dotýkat (mj.) dvou polí, z nichž každé bude nutně mít jinou barvu.

n = 4

Polem bude vynucována 4. barva, pokud se bude zároveň dotýkat (mj.) tří polí, z nichž každé bude nutně mít jinou barvu.

n = 5

Polem bude vynucována 5. barva, pokud se bude zároveň dotýkat (mj.) čtyř polí, z nichž každé bude nutně mít jinou barvu.

Na základě této úvahy se pokusíme zkonstruovat útvar vynucující 5. barvu, resp. budeme zkoumat závislost MAX (U) na struktuře mapy, a to tak, že postupně budeme přidávat pole a jejich doteky a zkoumat, jak se vzniklé útvary chovají při minimálním udílení barev. Postupně lze zjistit toto:

1. Jedno či více polí bez dotyku vynucuje 1 barvu:

2. Řetězy, lineární a rozvětvené, tj. obecně útvary neuzavírající plochy, bez "zpětné vazby", vynucují 2 barvy. Vznikají spojením dvou či více polí do neuzavřené jednoduché či větvící se linie, a to tak, že každé přidané pole spojíme vždy jen s jediným polem výchozího útvaru (počínaje dvěma poli vzájemně spojenými). O vzniklém řetězu (lineárním či rozvětveném) pak můžeme říci, že vynucuje dvě barvy, protože to plyne ze způsobu konstrukce: vyjdeme-li z elementárního řetězu, tvořeného dvěma vzájemně se dotýkajícími poli, z nichž tedy jedno má barvu 1 a druhé barvu 2, přidané pole se bude dotýkat jen jednoho pole, barvy buď 1, či 2, a může tedy mít buď barvu 2, nebo 1, a totéž platí pro každé další přidané pole.

3. Kruhy, obecně útvary uzavírající plochy, se "zpětnou vazbou". Lze rozlišit kruhy sudé, ty vynucují 2 barvy, a kruhy liché, jež vynucují 3 barvy. Liché kruhy vznikají tak, že se k řetězu přidá pole a spojí se se dvěma různými poli řetězu, jimž je minimálním udílením udělena různá barva (viz pozn. 2), takže přidané pole musí mít barvu odlišnou od barvy obou polí řetězu. Sudý kruh pak vzniká analogicky, ovšem spojením přidaného pole s poli řetězu, jimž je minimálním udílením udělena stejná barva (1, či 2), takže přidané pole může mít barvu zbývající (2, či 1). Kruh od sebe odděluje dvě dílčí plochy, vnitřní a vnější.

4. Z útvarů vynucujících 3. barvu můžeme přejít ke konstrukci útvarů vynucujících 4. barvu. Vznikají tak, že se do vnitřní či vnější plochy lichého kruhu přidá pole a spojí se se všemi dostupnými poli kruhu. Konstrukční zásada pospojování se všemi dostupnými poli kruhu je zdůvodněna jednak úvahou, že dotyk s poli tří barev vynutí čtvrtou barvu u přidaného pole, a jednak skutečností, že vynechání už jen jednoho dotyku umožní provést takové udílení barev (nezapomínejme, že nyní už udílíme barvy z množiny barev o třech barvách), že pole kruhu bez dotyku bude právě polem se třetí barvou, takže přidané pole bude moci mít také třetí barvu (a nebude muset mít čtvrtou).

Poznámka. Sdělení pod bodem 1 podle našeho soudu postihuje všechny útvary vynucující 1 barvu, v bodě 2 všechny otevřené útvary vynucující 2. barvu a v bodě 3 všechny uzavřené útvary vynucující 2. a 3. barvu. V bodě 4 jsme naznačili pouze rozvoj linie lichých kruhů k vynucování 4. barvy. Pro úplnost bychom měli zkoumat, jak se chovají i sudé kruhy při doplnění směřujícím k dosažení vynucování 3., resp. 4. barvy. Sudý kruh v zásadě můžeme doplnit polem dovnitř nebo ven a spojit je buď se dvěma různými poli, jimž jsou minimálním udílením uděleny různé barvy, a přidané pole pak bude nutně mít barvu třetí, takže vzniknou vlastně dva liché kruhy. Jak se chovají liché kruhy při doplnění, jsme již studovali. Nebo můžeme přidané pole spojit navíc s dalšími poli či se všemi poli. Podle situace pak vzniknou další liché kruhy, jejichž chování už známe, nebo také sudé kruhy s polem ve 3. barvě, případně elementární liché kruhy (tvořené třemi uzly a třemi hranami) - přímo se vnucuje pojmenovat jejich soubor (ač je to nepřesné) "trojúhelníková síť". Jak ta se chová, je popsáno v bodě 5.

Zmíněné sudé kruhy s polem ve třetí barvě mohou sloužit za východisko ke konstrukci útvarů vynucujících 4. barvu jen zdánlivě: při udílení z množiny tří barev existuje i udílení, při němž 4. barva není vynucována, i když přidané pole (nyní je to možné už pouze dovnitř sudého kruhu s polem ve 3. barvě) je spojeno se všemi poli sudého kruhu se třetí barvou:

Tím jsme vyčerpali všechny možnosti rozvoje sudých kruhů a zbývají jen liché kruhy, jejichž chování je popsáno v bodě 5.

5. Od útvarů vynucujících 4. barvu (bod 4) bychom zřejmě mohli dojít k útvarům vynucujícím 5. barvu tak, že přidáme pole a spojíme je s poli všech čtyř barev. Když se ale o to pokusíme, musíme konstatovat, že to není možné. Chceme-li přidat pole do poloplochy s polem s vynucenou 4. barvou, zjistíme, že je rozčleněna na dílčí plochy ohraničené třemi uzly a třemi hranami (již zmíněná "trojúhelníková síť"), takže přidané pole se může dotýkat jen tří polí se třemi různými barvami, a lze je tedy vybarvit čtvrtou (již jinde použitou) barvou. (Po přidání do dílčí plochy bez pole se 4. barvou pak jen zopakujeme postup vedoucí k vynucení 4. barvy.) Útvary vynucující 5. barvu tedy sestrojit nelze. (Viz pozn. 3.) Proto se odvažujeme tvrdit, že jsme dokázali platnost teorému (T).

Poznámky

(1) O tom viz zevrubnou zprávu Juraje Bosáka Ako bol vyriešený problém štyroch farieb, in: Pokroky matematiky, fyziky a astronomie, roč. XXIV (1979), č. 4, s. 181-201.

(2) Platí, že tato pole budou mít vždy různou barvu při libovolném minimálním udílení barev z množiny barev MB = (1, 2); při udílení z množiny barev MB = (1, 2, 3) to pak už pochopitelně neplatí.

(3) Útvary o určitém chování lze sestrojit podle našich logických úvah a jinak je zřejmě sestrojit není možné. Děláme vše možné pro to, abychom je sestrojili - a ono to nejde. Není to tedy možné.