Heawoodova hypotéza

Heawoodova domněnka , nebo Ringel-Yangsova věta, dává spodní hranici počtu barev, které jsou potřeba k obarvení grafu na povrchu s daným rodem . Tato hranice se nazývá povrchové chromatické číslo nebo Heawoodovo číslo. Pro povrchy rodu 0, 1, 2, 3, 4, 5, 6, 7, ... je požadovaný počet barev 4, 7, 8, 9, 10, 11, 12, 12, .... A000934 ,.

Hypotézu formuloval v roce 1890 Percy John Heawood a v roce 1968 ji dokázali Gerhard Ringel a Ted Youngs . Jeden případ, jmenovitě neorientovaná Kleinova láhev , je výjimkou z obecného vzorce. Zcela odlišný přístup byl zapotřebí pro mnohem starší problém zjištění počtu barev potřebných pro letadlo nebo kouli , který v roce 1976 vyřešili Wolfgang Haken a Kennthe Appel ( čtyřbarevný teorém ). Na kouli je snadné najít dolní hranici a na površích vyšších rodů je snadné najít horní hranici, a to bylo prokázáno v původním Heawoodově krátkém článku obsahujícím formulaci domněnky. Jinými slovy, k prokázání Ringelovy věty museli Youngs a další zkonstruovat extrémní příklady pro každý povrchový rod g = 1,2,3,.... Je-li g = 12s + k, rod povrchu se rozdělí na 12 případů podle ke zbytku k = 0,1,2,3,4,5,6,7,8,9,10,11. Roky, ve kterých bylo rozhodnuto ve dvanácti případech a kdo je rozhodl:

Posledních sedm samostatných výjimek bylo vyřešeno:

Formální prohlášení

Percy John Heawood v roce 1890 předpokládal , že pro daný rod g > 0 je minimální počet barev potřebný k vybarvení jakékoli kresby na orientovatelném povrchu tohoto rodu (nebo ekvivalentně k obarvení jakékoli části povrchu do jednoduše spojených domén) darováno

kde je funkce podlahy .

Sám Heawood věřil, že dokázal rovnost ve vzorci, ale již o rok později Heffter [1] upozornil na nepřesnosti v Heawoodově důkazu, takže nerovnost zůstala. Sám Heffter prokázal rovnost pro . V důsledku toho se tvrzení, že rovnost platí v Heawoodově vzorci, stalo známým jako Heawoodova domněnka o barvení map [2].

Nahrazením rodu Eulerovou charakteristikou získáme vzorec, který pokrývá jak orientovatelné, tak neorientovatelné případy,

Jak ukázali Ringel a Youngs, tato rovnost platí pro všechny povrchy kromě láhve Klein . Philip Franklin 1930 dokázal, že láhev Klein potřebuje maximálně 6 barev, nikoli 7, jak říká vzorec. Franklinův graf lze nakreslit na Kleinovu láhev tak, že se vytvoří šest párově hraničících oblastí, což ukazuje, že hranice je přesná.

Horní mez prokázaná v Heawoodově původním papíru je založena na algoritmu chamtivých barev . Manipulací s Eulerovou charakteristikou lze ukázat, že každý graf vložený do daného povrchu musí mít alespoň jeden vrchol se stupněm menším, než je zadaná hraniční hodnota. Pokud odstraníme tento vrchol a obarvíme zbývající graf, malý počet hran dopadajících na odstraněný vrchol umožní přidat vrchol zpět a dát mu barvu, aniž by se zvýšil počet potřebných barev. V opačném směru je důkaz složitější a ukazuje, že ve všech případech (s výjimkou Kleinovy ​​láhve) lze do plochy vložit kompletní graf s počtem vrcholů rovným danému počtu barev.

Příklad

Pro torus je g = 1, takže χ = ​​0. Jak vyplývá ze vzorce, jakékoli rozdělení torusu na oblasti může být obarveno sedmi barvami. Obrázek ukazuje rozdělení torusu, ve kterém každý ze sedmi regionů hraničí s každým dalším regionem. Toto rozdělení ukazuje, že sedmibarevný okraj je pro tento případ přesný. Hranice tohoto oddílu tvoří vložení Heawoodova grafu do torusu.

Poznámky

  1. ↑ Heffter, 1891 , str. 477-508.
  2. ↑ Harari, 2003 , str. 162.

Literatura

Odkazy