Vizingova věta

Vizingův teorém je výrokem teorie grafů , podle kterého mohou být hrany libovolného jednoduchého neorientovaného grafu obarveny řadou barev , nejvýše o jednu větší, než je maximální stupeň vrcholů grafu. Vzhledem k tomu , že barev je vždy dostatek, lze všechny neorientované grafy rozdělit do dvou tříd – grafy „první třídy“, pro které je barev dostatek, a „druhé třídy“, pro kterou jsou barvy potřeba. $\Delta$ $\Delta +1$ $\Delta$ $\Delta +1$

Výsledek založil Vadim Vizing v roce 1964 .

Příklady

Pokud , v grafu nejsou žádné sousední hrany a hrany mohou být obarveny stejnou barvou. Všechny grafy s tedy patří do první třídy. $\Delta =1$ $G$ $\Delta (G)=1$

Pokud , graf musí být disjunktním spojením cest a cyklů . Pokud jsou všechny cykly sudé, jejich okraje mohou být obarveny dvěma barvami, přičemž barvy se postupně mění a procházejí každým cyklem. Pokud však existuje alespoň jeden lichý cyklus, jeho okraje nemohou být dvoubarevné. Graf c tedy patří do první třídy právě tehdy, když je bipartitní . $\Delta =2$ $G$ $\Delta =2$

Pro multigrafy obecně Vizingův teorém neplatí. Například multigraf vytvořený zdvojením každé hrany trojúhelníku má maximálně čtyři stupně, ale okraje tohoto grafu nemohou být obarveny méně než šesti barvami.

Klasifikace grafů

Někteří autoři stanovili další podmínky pro to, aby některé grafy patřily do první nebo druhé třídy, ale úplná klasifikace neexistuje. Pokud například vrcholy maximálního stupně v grafu tvoří nezávislou množinu , nebo obecněji, pokud je vygenerovaným podgrafem pro tuto množinu vrcholů les, pak bude patřit do první třídy [1] . $\Delta$ $G$ $G$

Erdős a Wilson [2] ukázali, že téměř všechny grafy patří do první třídy. Takže v modelu náhodných Erdős-Rényiho grafů , ve kterém jsou všechny grafy s vrcholy stejně pravděpodobné, označme pravděpodobnost, že graf s vrcholy patří do první třídy. Pak inklinuje k jednotě jako k nekonečnu. Později vyvinul jemnější odhady míry snahy o jednotu [3] . $n$ $p(n)$ $n$ $p(n)$ $n$ $p(n)$

Rovinné grafy

Vizáž [4] ukázala, že rovinný graf patří do první třídy, pokud je jeho maximální stupeň alespoň osm. Všiml si však, že pro stupeň maximálně dva až pět existují rovinné grafy druhé třídy. Pro stupně dva je takovým grafem jakýkoli lichý cyklus a pro stupně tři, čtyři a pět lze takové grafy sestavit z pravidelných polytopů nahrazením hran na cestě párů sousedních hran.

Vizingova domněnka o rovinných grafech [4] uvádí, že všechny jednoduché rovinné grafy s maximálním stupněm šest a sedm patří do první třídy, což uzavírá zbývající možnosti. V roce 2001 [5] bylo zjištěno , že všechny rovinné grafy s maximálním stupněm sedm patří do první třídy. V otázce tak zůstává pouze případ s maximálním výkonem šest. Tato domněnka poskytuje pozadí pro celkovou domněnku o zbarvení .

Rovinné grafy druhé třídy, budované z pravidelných polytopů dělením hran, nejsou pravidelné - mají jak vrcholy druhého řádu, tak vrcholy vyšších řádů. Čtyřbarevný teorém o obarvení vrcholů rovinného grafu je ekvivalentní tvrzení, že jakýkoli 3-běžný bezmůstkový graf patří do první třídy [6] (toto tvrzení je pravdivé s ohledem na důkaz čtyřbarevnosti teorém).

Grafy na nerovných plochách

V roce 1969 Branko Grünbaum předpokládal, že každý 3-pravidelný graf, který má polyhedrální vnoření v jakékoli dvourozměrně orientované manifoldu , jako je torus , musí patřit do první třídy. V tomto kontextu polytopové vložení znamená vložení grafu tak, že jakákoli výsledná plocha grafu je topologicky ekvivalentní disku a takový, že duální graf je jednoduchý, bez smyček nebo vícenásobných sousedství. Pokud by to byla pravda, šlo by o zobecnění věty o čtyřech barvách, což, jak ukázal Tate, je ekvivalentní tvrzení, že jakýkoli 3-pravidelný graf, pro který je v kouli vnořen polytop, je v první třídě. V roce 2009 [7] se však ukázalo, že domněnka není pravdivá, když byly nalezeny hady , které mají zabudování ve formě mnohostěnů v orientovaných plochách vysokého rodu . Na základě této konstrukce také ukázal, že určení, zda graf s polytopovým vnořením patří do první třídy, je NP-úplný problém [8] .

Algoritmy

V roce 1992 [9] popsal algoritmus pro polynomiální časové vybarvování libovolného grafu pomocí barev, kde je maximální stupeň grafu. Algoritmus tedy používá optimální počet barev pro grafy druhé třídy a pro všechny grafy používá maximálně jednu barvu navíc. Algoritmus používá stejnou strategii jako původní důkaz Vizingovy věty - algoritmus začíná bezbarvým grafem a postupně hledá barvicí cesty tak, aby do obarvení byla zahrnuta jedna hrana navíc. $\Delta +1$ $\Delta$

Popis algoritmu používá termíny "ventilátor", "rotace ventilátoru" a " -cesta", které zavedli autoři algoritmu [10] , jakož i následující konvenci: barva je ve vrcholu volná, pokud existují žádné barevně zbarvené okraje nedopadají na vrchol . Algoritmus provádí následující kroky: $cd$ $d$ $w$ $d$ $w$

Pro každou neobarvenou hranu v částečně barevném grafu je zkonstruována sekvence - maximální vějíř. $UV$ $\left\langle v,...,l\right\rangle$
- Pro každou dvojici barev , kde je barva volná ve vrcholu a je volná barva v , se vykreslí barvy -cesty. $c, d$ $C$ $u$ $d$ $l$ $cd$
- Vrchol je vybrán tak, že jde o podřetězec a nepoužívá se v . $w$ $\left\langle v,...,w\right\rangle$ $\left\langle v,...,l\right\rangle$ $d$ $w$
- Ventilátor se "otáčí", je barevně lakován . $\left\langle v,...,w\right\rangle$ $ww$ $d$

Vějíř je posloupnost vrcholů s následujícími vlastnostmi: $\left\langle v_{0},...,v_{r}\right\rangle$

všechny vrcholy jsou sousedy vrcholu a $u$ $v_{0}=v$
hrana je natřena barvou , která nebyla použita ve vrcholech $u\,v_{k+1}$ $d_{k}$ $\left\langle v_{0},\ldots ,v_{k}\right\rangle$

Vějíř lze otáčet , tj. barvy okrajů lze nahradit barvami okrajů a tato permutace barev nenarušuje vybarvení grafu. ${\displaystyle uv_{k))$ $uv_{k+1}$

$cd$ -path je maximální posloupnost hran začínajících v a každá hrana je obarvena v nebo . Převrácení barev tohoto řetězu znamená nahrazení za . $u$ $C$ $d$ $C$ $d$ $d$ $C$

Všechny operace použité v algoritmu neničí zbarvení grafu a po obrácení barev -cesty existuje podřetězec popsaný v algoritmu. $cd$

Pomocí jednoduché datové struktury pro uložení barev použitých ve vrcholu lze celý krok algoritmu dokončit v čase , kde je počet vrcholů v grafu. Protože se každý krok musí opakovat pro všechny oblouky, bude celkový čas . $Na)$ $n$ $m$ $O(mn)$

V nepublikovaném článku v roce 1985 [11] bylo uvedeno, že je možné najít zbarvení v čase . $O(m{\sqrt n}\log n)$

Historie

Předpokládá se [12] [13] , že Vizingova práce byla inspirována Shannonovým teorémem [14] , který ukazuje, že multigrafy lze vybarvit pomocí nejvýše barev. Existuje také názor, že Vizing měl problémy s publikací výsledku (poprvé publikovaného v časopise „Discrete Analysis“, publikovaném před rokem 1991 Ústavem matematiky sibiřské pobočky Akademie věd SSSR , který západní autoři nazývají „ málo známé“ [12] ). ${\tfrac {3}{2}}\Delta$

Viz také

Brooksův teorém , vztahující zbarvení vrcholu na maximální stupeň.

Poznámky

↑ Fournier, 1973 .
↑ Erdős, Wilson, 1977 .
↑ Frieze, Jackson, McDiarmid, Reed, 1988 .
↑ 1 2 Vizing, 1965 .
↑ Sanders, Zhao, 2001 .
↑ Tait, 1880 .
↑ Kochol, 2009 .
↑ Kochol, 2010 .
↑ Misra, Gries, 1992 .
↑ Popis algoritmu převzat z článku Joachima Breitnera. Dokazování Vizingovy věty s Rodinem. — 2011.
↑ Gabow a kol., 1985 .
↑ 12 Gutin, Toft, 2000 .
↑ Soifer, 2008 .
↑ Shannon, 1949 .

Literatura

K. Appel, W. Haken. Každá rovinná mapa je čtyřbarevná // Bulletin American Mathematical Society. - 1976. - T. 82 , čís. 5 . — S. 711–712 . - doi : 10.1090/S0002-9904-1976-14122-5 .
Paul Erdős, Robin J. Wilson. Poznámka k chromatickému indexu téměř všech grafů // Journal of Combinatorial Theory . - 1977. - T. 23 , no. 2–3 . — S. 255–257 . - doi : 10.1016/0095-8956(77)90039-9 .
Jean-Claude Fournier. Colorations des arêtes d'un graphe // Cahiers du Centre d'Études de Recherche Opérationnelle. - 1973. - T. 15 . — S. 311–314 .
Alan M. Frieze, B. Jackson, CJH McDiarmid, B. Reed. Náhodné grafy zbarvující okraje // Journal of Combinatorial Theory . - 1988. - T. 45 , no. 2 . — S. 135–149 . - doi : 10.1016/0095-8956(88)90065-2 .
Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algoritmy pro vybarvování hran grafů. - Univerzita Tohoku, 1985. - (Tech. zpráva TRECIS-8501).
Gregory Gutin, Bjarne Toft. Rozhovor s Vadimem G. Vizingem // Newsletter European Mathematical Society. - 2000. - T. 38 , no. prosince . — S. 22–23.
Martin Kochol. Proceedings of the American Mathematical Society. - 2009. - T. 137. - S. 1613-1619.
Martin Kochol. Složitost 3hranného vybarvování ve třídě kubických grafů s polyedrickým zapuštěním do orientovatelné plochy // Diskrétní aplikovaná matematika. - 2010. - T. 158 , č.p. 16 . - S. 1856-1860 . - doi : 10.1016/j.dam.2010.06.019 .
Konstruktivní důkaz Vizingovy věty // Information Processing Letters . - 1992. - T. 41 , no. 3 . — S. 131–133 . - doi : 10.1016/0020-0190(92)90041-S .
Daniel P. Sanders, Yue Zhao. Rovinné grafy maximálního stupně sedm jsou třídy I // Journal of Combinatorial Theory . - 2001. - T. 83 , no. 2 . — S. 201–212 . - doi : 10.1006/jctb.2001.2047 .
Claude Shannon. Věta o vybarvování čar sítě // J. Math. Fyzika. - 1949. - T. 28 . — S. 148–151 .
Alexander Soifer. Matematická omalovánka. - 2008. - S. 136-137 . — ISBN 978-0-387-74640-1 .
PG Tait. Poznámky k barvám map // Proc. R. Soc. Edinburgh. - 1880. - T. 10 . - S. 729 .
V. G. Vizing. O odhadu chromatické třídy p-grafu // Sat. Diskrétní analýza. - Novosibirsk: Ústav matematiky sibiřské pobočky Akademie věd SSSR, 1964. - T. 3 . — S. 25–30 .
V. G. Vizing. Kritické grafy s danou chromatickou třídou // Sat. Diskrétní analýza. - Novosibirsk: Ústav matematiky sibiřské pobočky Akademie věd SSSR, 1965. - V. 5 . — S. 9–17 .

Odkazy

Důkaz Vizingovy věty v PlanetMath .