Úvod

Teorém čtyř barev byl poprvé formulován Francisem Guthrie někdy kolem roku 1852. Spočívá v tom, že libovolný plošný obrazec (graf) rozdělený na libovolný konečný počet menších obrazců je vybarvitelný nejvýše čtyřmi barvami tak, aby žádné dva sousední obrazce neměly stejnou barvu. Obrazce mohou stejnou barvou sousedit pouze v rozích (tvary, na kterých se oblasti vyskytují, přirozeně mění minimální počet barev, který je potřeba, např. třírozměrný toroid potřebuje barev sedm).
Tato zdánlivě velice prostá hypotéza (pro plošný obrazec) se ukázala jako velice těžko dokazatelná. První důkaz, který je současně i návodem jak postupovat vyslovil A.B.Kempe 1879 spočívá v redukci počtu obrazců (oblastí). Nalezneme oblasti, které mají méně jak tři sousedy, tj. jedna barva potřebná k vybarvení právě těchto oblastí nám ještě zbývá a odstraníme je z obrazce. Pokud 2 kandidáti spolu sousedí, pak jsou zbývající barvy dvě, takže na vybarvení oblastí mám zase ještě dvě barvy, Pokud spolu sousedí 3 kandidáti, tak mám jenom jednu oblast navíc a 3 barvy na vybarvení, pokud spolu souvisí všichni kandidáti, tak víc oblastí, jak 4 v obrazci nejsou.

Tento důkaz se ale ukázal jako nedostatečný. Odkaz obsahuje ukázku takového grafu, který je možné redukovat: Teorém čtyř barev. Obrazec na této stránce lze ale velmi jednoduše upravit tak, že už nebude možné jej tímto postupem redukovat (stačí zvětšit plochy A, C, E tak, aby se vzájemně dotýkaly při zachovní všech ostatních styčných hran).

Další metoda známá jako metoda Kempeho řetězců (od stejného autora) je modifikací výše popsaného postupu a odstraňuje problém redukovalelnosti, ale jak se ukázalo později, ani tato metoda není zcela správná, navíc již není tak snadno algoritmovatelná. Vlastní důkaz trval dalších více jak 150 let a má se za to, že Appel Hakenův důkaz z roku 1976 a poté vylepšený Robertson Sandersův důkaz z roku 1996 jsou již definitivní, jakkoli jsou také již nad moje možnosti. Oba důkazy spočívají na vytváření konfigurací a dokazování, že každý další diagram lze zredukovat (jiným způsobem, než v původním důkazu) na jednu z těchto konfigurací a že počet konfigurací je u konečné velikosti grafu konečný (pokud jsem to správně pochopil). Haesch v roce 1969 použil metodu redukce náboje a předpokládal, že počet konfigurací je asi 8900, Appel a Haken důkaz provedli s asi 1500ti konfiguracemi, Robertson se Sandersem zredukovali takzvanou nevyhnutelnou množinu konfigurací na 633. Výše uvedený popis ukazuje (i vzhledem k některým na tomto místě nevysvětleným pojmům) na to, jak se postupně vyvíjela celá teorie potřebná k tomu, aby byl důkaz podán. Podrobnější popis získáte na Wikipedii v angličtině, nebo na The four color theorem Robertson, Sanders, Seymour, Thomas.

Celá záležitost je o to zajímavější, že to, co lze dokázat tak komplikovaně, je při praktickém užití schopno zvládnout na několik pokusů i dítě na prvním stupni základní školy, viz. první z odkazů; jak plochy obarvit zjistíme velmi rychle dokonce i v případě, kdy graf není redukovatelný.

Tento úvod je zde proto, abych vysvětlil, proč jsem k problému přistoupil heuristicky (slušně řečeno, jinak se tomu také říká, pokus, omyl).

Algoritmus

Řešení vychází ze skutečného praktického použití, kdy je potřeba čtvercovou (obdélníkovou) matici vybarvit podle potřeby uživatele, který si definuje jednotlivé součásti konstrukce (obrazce) z menších čtverců (obdélníků), kterým budu říkat součásti. Jednotlivé obrazce mají jediné omezení, musí být spojité, tj. každá součást jednoho obrazce sousedí s jinou alespoň jednou hranou. Algoritmus se vyvíjel postupně a protože jde o heuristický algoritmus z obou pohledů tj. způsobu nalezení i způsobu provádění, nemohu prokázat, že vždy povede k cíli. Pokud někdo nalezne příklad, kdy algoritmus selže, budu vděčný. Prakticky však se zatím během používání nestalo, aby konstrukce měly tak komlikovaný tvar, aby vybarvení selhalo.

Vlastní vybarvování je prováděno po jednotlivých řádcích zprava doleva a shora dolů podle součástí. Tak jsou orientované i souřadnice. Tento způsob se ukázal jako nejúspěšnější. Pokud vybarvování selže, vymažu poslední konstrukci, zarotuji barvy (tj. posunu se další barvu dál) a zkusím to znovu, pokud vybarvování znovu selže, vrátím se o dva kroky zpět, opět zarotuji barvy a opět to zkusím, atd... Algoritmus z tohoto pohledu nepatří k nejúspornějším, u velkého počtu prvků bude asi pomalý. Pro zobecnění by možná bylo vhodnější, než čtverce použít trojúhelníky, ale pro účely, pro které byl algoritmus použitý se čtverce (obdélníky) lépe hodí. Program byl vyvinutý v prostředí JDeveloper a dodatečně přenesený do NetBeans. Byl upravený tak, aby nekolidoval s vlastnostmi Java 1.5.

Pro úplnost dodávám, že program je sice součástí určitého komerčního balíku, ale byl vyvinut mimo moji pracovní dobu v době dovolené, vzhledem k časové náročnosti (řádově desítky hodin), a teprve poté zdarma firmě poskytnut. Proto si osobuji právo s ním nakládat podle vlastního uvážení, v tomto případě jej poskytnout komukoli, kdo má o něj zájem.

Program ColourIt je v přiložených souborech, soubory stačí zkompilovat. Main sekce jsou v PJCSchJawt.java (rekurzívní varianta) a v PJCSchemaJ.java (iterativní varianta).

Seznam souborů:

  • ColourItI.java
  • ColourItR.java
  • Console.java
  • Counter.java
  • CounterComparator.java
  • CtyriDvojice.java
  • PJCSchJawt.java
  • PJCSchemaJ.java
  • XYConstraints.java
  • XYLayout.java
  • schLabel.java

Soubory jsou nevyčištěné, je zde hodně nadbytečného kódu. Některé poznámky jsou v angličtině, je to zvyk, přestože anglicky moc neumím, anglický text se při přenesení z jednoho OS do jiného (například Windows JDeveloper - Linux NetBeans) nepokazí, zatímco čeština s háčky a čárkami skoro vždy.