Ú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.