Gallai-Hasse-Roy-Vitaverova věta

Gallai-Hasse-Roy-Vitaverova věta je druh duality mezi zbarvením vrcholů daného neorientovaného grafu a orientací jeho hran. Věta říká, že minimální počet barev potřebný pro správné obarvení libovolného grafu G je o jednu větší než délka maximální cesty v orientaci grafu G , ve které je tato délka cesty minimální [1] . Orientace, ve kterých má dráha maximální délky minimální délku, obsahují vždy alespoň jednu acyklickou orientaci [2] .

Alternativní formulace stejné věty říká, že jakákoli orientace grafu s chromatickým číslem k obsahuje jednoduchou orientovanou cestu s k vrcholy [3] . Je možné klást podmínky tak, aby cesta začínala v libovolném vrcholu a aby z tohoto vrcholu bylo možné dosáhnout jakéhokoli jiného vrcholu orientovaného grafu [4] [5] .

Příklady

Bipartitní graf lze orientovat z jedné části do druhé. Nejdelší cesta v této orientaci má pouze dva vrcholy. Naopak, pokud orientace v grafu neobsahuje cestu délky tři, pak jakýkoli vrchol musí být buď zdrojem (žádné příchozí oblouky) nebo jímkou ​​(žádné odchozí oblouky), a rozdělení vrcholů na zdroj a výlevky ukazuje, že toto graf je bipartitní.

V jakékoli orientaci cyklu grafu liché délky není možné dát všem sousedním hranám různé směry, takže dvě po sobě jdoucí hrany tvoří cestu se třemi vrcholy. V souladu s tím je chromatický počet lichých cyklů tři.

Důkaz

Abychom dokázali, že chromatické číslo je větší nebo rovno minimální délce maximální cesty, předpokládejme, že graf je obarven k barvami pro nějaké k . Potom lze graf orientovat acyklicky očíslováním barev a každou hranu směřovat od barvy s nižším indexem k vyšší. V této orientaci se barevné indexy striktně zvyšují podél jakékoli orientované cesty, takže každá cesta obsahuje nejvýše jeden vrchol každé barvy a celkový počet vrcholů v cestě nemůže překročit k (počet barev).

Abychom dokázali, že chromatické číslo je menší nebo rovno minimální délce maximální cesty, předpokládejme, že graf má orientaci, ve které je na libovolné orientované cestě pro nějaké k nejvýše k vrcholů . Vrcholy grafu lze obarvit k barvami tak, že si vyberete podgraf s maximální acyklickou orientací a poté obarvíte každý vrchol barvou s indexem rovným délce nejdelší cesty k danému vrcholu. Při takovém zabarvení je každá hrana podgrafu orientována z vrcholu s nižším indexem do vrcholu s vyšším indexem, a proto bude vybarvení správné. Pro každou hranu, která nepatří do podgrafu, musí být uvnitř podgrafu nasměrovaná cesta spojující tyto dva vrcholy v opačném směru, jinak by hrana spadla do podgrafu. Okraj je tedy orientován z většího čísla na menší a nenarušuje správnost vybarvení [6] .

Důkaz této věty použil Yury Vladimirovich Matiyasevich jako testovací případ pro navrhované schéma důkazu v diskrétní matematice [7] .

Interpretace z hlediska kategorií

Věta má přirozenou interpretaci v kategoriích orientovaných grafů a grafových homomorfismů . Homomorfismus je mapování vrcholů jednoho grafu na vrcholy jiného grafu, ve kterém sousední vrcholy zůstávají v obraze sousedící. Potom lze k -zabarvení neorientovaného grafu G popsat homomorfismem grafu G do úplného grafu K k . Za předpokladu orientace v úplném grafu se z něj stane turnaj , a tuto orientaci lze použít ke specifikaci orientace v grafu G . Konkrétně zbarvení dané nejdelší cestou odpovídá homomorfismu do tranzitivního turnaje (acyklicky orientovaného kompletního grafu) a jakékoliv zbarvení lze tímto homomorfismem popsat do tranzitivního turnaje.

Uvažujeme-li homomorfismy v opačném směru, do G , nikoli z G , je orientovaný graf G acyklický a má nejvýše k vrcholů na nejdelší dráze právě tehdy, když neexistuje homomorfismus cesty P k  + 1 ke G .

Gallai-Hasse-Roy-Vitaverova věta je tedy ekvivalentní větě, že pro jakýkoli orientovaný graf G existuje homomorfismus do tranzitivního turnaje s k vrcholy právě tehdy, když neexistuje homomorfismus z cesty s ( k  + 1) vrcholy [2] . V případě, že je graf G acyklický, lze za formu věty považovat tvrzení , že nejdelší řetězec v částečně uspořádané množině je roven minimálnímu počtu antiřetězců, na které lze množinu rozdělit [8 ] . Tvrzení lze zobecnit z cest k jiným orientovaným grafům — pro jakýkoli polytree P existuje duální orientovaný graf D takový, že pro jakýkoli orientovaný graf G existuje homomorfismus od G do D právě tehdy, když neexistuje izomorfismus z P až G [9] .

Historie

Gallai-Hasse-Roy-Vitaverova věta byla opakovaně znovuobjevena [2] . Věta získala své jméno podle samostatných publikací T. Gallaie [10] , M. Hasse [11] , B. Roye [12] a L. M. Vitavera [13] . Roy připisuje formulaci teorému Claude Berge , který ji uvedl jako domněnku v knize o teorii grafů v roce 1958 [12] .

Poznámky

  1. Hsu, Lin, 2009 , str. 129–130.
  2. 1 2 3 Nešetřil, Ossona de Mendez, 2012 , str. 42.
  3. Chartrand, Zhang, 2009 .
  4. Li, 2001 , str. 681–685.
  5. Chang, Tong, Yan, Yeh, 2002 , str. 441–444.
  6. Hsu, Lin, 2009 , pp. 129-130.
  7. Matiyaševič, 1974 , s. 94–100.
  8. Mirsky, 1971 , str. 876–877.
  9. Nešetřil, Tardif, 2008 , str. 254–260.
  10. Gallai, 1968 , s. 115–118.
  11. Hasse, 1965 , str. 275–290.
  12. 1 2 Roy, 1967 , str. 129–132.
  13. Vitaver, 1962 , str. 758–759.

Literatura