Krycí graf

Graf C je krycím grafem jiného grafu G , pokud existuje krycí zobrazení z vrcholové množiny C do vrcholové množiny G . Krycí zobrazení f je surjekce a lokální izomorfismus — okolí vrcholu v v C se bijektivně zobrazuje na okolí f ( v ) v G .

Termín lifting se často používá jako synonymum pro pokrytí grafu spojeného grafu.

V teorii grafů může krycí graf také odkazovat na podgraf, který obsahuje buď všechny hrany ( pokrytí hran ) nebo všechny vrcholy ( pokrytí vrcholu ).

Kombinatorická formulace krycích grafů okamžitě zobecňuje na případ multigrafů . Ztotožníme-li multigraf s jednorozměrným buněčným komplexem, není krycí graf nic jiného než speciální příklad pokrytí topologických prostorů , takže je přípustná terminologie teorie pokrytí, jmenovitě transformační grupa pokrytí, univerzální pokrytí. , abelovské krytí a maximální abelovské krytí [1] .

Definice

Nechť a být dva grafy a nechť funkce je surjektivní . Pak f je krycí mapa od C do G , jestliže pro každé omezení f na okolí v je bijekce na okolí f ( v ) v G. Jinými slovy, f mapuje hrany spadající do v jedna ku jedné na hrany spadající do f ( v ). $G=(V_{1},E_{1})$ $C=(V_{2},E_{2})$ $f\colon V_{2}\to V_{1}$ $v\in V_{2}$

Pokud existuje krycí zobrazení od C do G , pak C je krycí graf nebo zdvih G a G je podílový graf C . H-výtah je takový výtah, že krycí mapa f má tu vlastnost, že pro jakýkoli vrchol v z G má jeho svazek přesně h prvků. $f^{-1}(v)$

Příklady

Na následujícím obrázku je graf C krycím grafem grafu H.

Krycí zobrazení f od C do H se odráží v barvách. Například oba modré vrcholy C se zobrazují na modré vrcholy grafu H . Zobrazení f je surjektivní — každý vrchol grafu H má předobraz v C . Navíc f zobrazuje bijektivně každého souseda vrcholu v z grafu C na souseda vrcholu f ( v ) z grafu H.

Nechť v je například jeden z purpurových vrcholů z C . Má dva sousedy v C , zelený vrchol u a modrý vrchol t . Podobně nechť v je purpurový vrchol H . Má dva sousedy v H , zelený vrchol u ′ a modrý vrchol t ′. Mapa f omezená na { t , u , v } je bijekce v { t ′, u ′, v ′}. To je znázorněno na následujícím obrázku:

Podobně můžeme zkontrolovat, že okolí modrého vrcholu v C mapuje jedna ku jedné na okolí modrého vrcholu v H :

Dvojité pokrytí

Ve výše uvedeném příkladu má každý vrchol H přesně 2 předobrazy v C . Zde H je 2-násobné krytí nebo dvojité krytí grafu C .

Pro jakýkoli graf G lze zkonstruovat dvojité bipartitní pokrytí grafu G , které je současně bipartitním grafem i dvojitým pokrytím G. Dvojité pokrytí grafu G v bipartitním grafu je tenzorový součin : ${\displaystyle G\times K_{2))$

Pokud je graf G již bipartitní, jeho dvojitý bipartitní obal se skládá ze dvou disjunktních kopií grafu G . Graf může mít mnoho různých dvojitých krytů jiných než dvojité pokrytí bipartitního grafu.

Univerzální krytina

Pro libovolný souvislý graf G lze sestrojit jeho univerzální krycí graf [2] . Jedná se o speciální případ obecnějšího pojetí univerzálního pokrytí z topologie. Topologický požadavek, aby bylo univerzální pokrytí jednoduše spojeno, se z hlediska teorie grafů překládá do požadavku, aby graf byl souvislý a neměl žádné cykly, tedy byl stromem . Graf univerzálního krytu je jedinečný (až do izomorfismu). Pokud je graf G strom, pak G sám je univerzálním krycím grafem G. Pro jakýkoli jiný konečně souvislý graf G je univerzálním krycím grafem G spočetně nekonečný (ale lokálně konečný) strom.

Graf univerzálního krytu T souvislého grafu G lze sestrojit následovně. Jako výchozí bod zvolíme libovolný vrchol r grafu G. Každý vrchol T je nevratný průchod, který začíná v r , to je posloupnost vrcholů v G taková, že $w=(r,v_{1},v_{2},\dots ,v_{n})$

v i a v i +1 sousedí v G pro všechna i , tj. w je průchod
$v_{i-1}\neq v_{i+1}$ pro všechna i , tj. žádný návrat.

Pak dva vrcholy T sousedí, pokud je jeden jednoduchým prodloužením druhého, pak vrchol sousedí s vrcholem . Až do izomorfismu se získá stejný strom T bez ohledu na volbu výchozího bodu r . $(r,v_{1},v_{2},\dots ,v_{n})$ $(r,v_{1},v_{2},\dots ,v_{n-1})$

Krycí zobrazení f mapuje vrchol ( r ) z T do vrcholu r v G a vrchol z T do vrcholu v n v G . $(r,v_{1},v_{2},\dots ,v_{n})$

Příklady univerzálních krytů

Následující obrázek ilustruje univerzální krycí graf T pro H . Barvy ukazují překryvný displej.

Pro libovolné k mají všechny k - regulární grafy stejné univerzální pokrytí, nekonečný k - regulární strom.

Topologický krystal

Nekonečně složený Abelův krycí graf konečného (multi)grafu se nazývá topologický krystal, abstrakce krystalové struktury, a je periodickým grafem . Například krystal diamantu jako graf je maximální abelovský krycí graf dipólu se čtyřmi hranami. Tento pohled v kombinaci s myšlenkou „standardních implementací“ se ukazuje jako užitečný při systematické konstrukci (hypotetických) krystalů [1] .

Rovinná krytina

Rovinné pokrytí grafu je konečné pokrytí grafu rovinným grafem . Vlastnost mít rovinný kryt může být popsána zakázanými nezletilými , ale přesný popis tohoto druhu zůstává neznámý. Jakýkoli graf vložený do promítací roviny má rovinný kryt získaný z orientovatelného dvojitého krytu promítací roviny. V roce 1988 Seiyu Nagami předpokládal, že pouze tyto grafy mají rovinné kryty, ale domněnka zůstává neprokázaná [3] .

Stresové grafy

Obecný způsob, jak získat krycí grafy, používá grafy napětí , ve kterých jsou "šipky" daného grafu G (tj. dvojice směrovaných hran odpovídající neorientovaným hranám G ) označeny dvojicemi protilehlých prvků (tj. prvek a jeho inverzní) z nějaké skupiny . Graf získaný z grafu napětí (odvozený graf) má jako vrcholy dvojice ( v , x ), kde v je vrchol grafu G a x je prvek grupy. Šipka od v do w označená prvkem skupiny y z G odpovídá hraně od ( v , x ) do ( w , xy ) v odvozeném grafu.

Na univerzální pokrytí lze v tomto přístupu nahlížet jako na odvozený graf grafu napětí, ve kterém jsou okraje kostry grafu označeny prvkem identity skupiny a každý zbývající pár šipek je označen různými prvky. z volné skupiny . Bipartitní dvojitý kryt si pak lze představit jako odvozený graf grafu napětí, ve kterém je každá šipka označena nenulovým prvkem skupiny řádu dva.

Poznámky

↑ 12. Sunada , 2012 .
↑ Angluin, 1980 , str. 82–93.
↑ Hliněny, 2010 , str. 525–536.

Literatura

Toshikazu Sunada. Topologická krystalografie – s výhledem na diskrétní geometrickou analýzu –. — Springer, 2012.
Petr Hlinený. 20 let Negamiho domněnky planárního krytu // Grafy a kombinatorika. - 2010. - T. 26 , no. 4 . — S. 525–536 . - doi : 10.1007/s00373-010-0934-9 .
Chris Godsil, Gordon Royle. Sekta. 6.8 // Teorie algebraických grafů. - Springer, 2004.
Amit Alon, Nathan Linial, Jiří Matoušek, Eyal Rozenman. Náhodné zdvihy grafů // Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 7-9 January (SODA 2001). - 2001. - S. 883-894. — ISBN 0-89871-490-7 .
Dana Angluinová. Lokální a globální vlastnosti v sítích procesorů // Sborník z 12. výročního sympozia ACM na téma Theory of computing (STOC 1980) . - 1980. - ISBN 0-89791-017-6 .