Graficul de acoperire

Un grafic C este un grafic de acoperire al altui grafic G dacă există o mapare de acoperire de la mulțimea de vârfuri C la mulțimea de vârfuri G. Maparea de acoperire f este o suprajecție și un izomorfism local — o vecinătate a unui vârf v în C se mapează bijectiv la o vecinătate a lui f ( v ) în G .

Termenul de ridicare este adesea folosit ca sinonim pentru acoperirea graficului unui grafic conectat.

În teoria grafurilor, un graf de acoperire se poate referi și la un subgraf care conține fie toate muchiile ( acoperirea marginilor ) fie toate vârfurile ( acoperirea vârfurilor ).

Formularea combinatorie a graficelor de acoperire se generalizează imediat în cazul multigrafelor . Dacă identificăm un multigraf cu un complex de celule unidimensionale, graficul de acoperire nu este altceva decât un exemplu special de acoperiri ale spațiilor topologice , astfel încât este permisă terminologia teoriei acoperirii, și anume grupul de transformare al învelișului, învelișul universal. , învelișul abelian și învelișul abelian maxim [1] .

Definiție

Fie și două grafice și fie funcția surjectivă . Atunci f este o hartă de acoperire de la C la G dacă, pentru fiecare, restricția lui f la o vecinătate a lui v este o bijecție la o vecinătate a lui f ( v ) în G. Cu alte cuvinte, f mapează muchiile incidente cu v unu-la-unu cu muchiile incidente cu f ( v ). $G=(V_{1},E_{1})$ $C=(V_{2},E_{2})$ $f\colon V_{2}\to V_{1}$ $v\in V_{2}$

Dacă există o mapare de acoperire de la C la G , atunci C este un grafic de acoperire sau lift al lui G , iar G este un grafic de coeficient al lui C. Un h-lift este o ridicare astfel încât harta de acoperire f are proprietatea că pentru orice vârf v al lui G , pachetul său are exact h elemente. $f^{-1}(v)$

Exemple

În figura următoare, graficul C este graficul de acoperire al graficului H.

Maparea acoperirii f de la C la H este reflectată în culori. De exemplu, ambele vârfuri albastre ale lui C se mapează cu vârfurile albastre ale graficului H . Maparea f este surjectivă - fiecare vârf al graficului H are o preimagine în C . Mai mult, f mapează bijectiv fiecare vecin al vârfului v din graficul C la un vecin al vârfului f ( v ) din graficul H.

De exemplu, să fie v unul dintre vârfurile magenta din C . Are doi vecini în C , un vârf verde u și un vârf albastru t . În mod similar, fie v vârful magenta al lui H . Are doi vecini în H , un vârf verde u ′ și un vârf albastru t ′. Harta f limitată la { t , u , v } este o bijecție în { t ′, u ′, v ′}. Acest lucru este ilustrat în următoarea figură:

În mod similar, putem verifica dacă vecinătatea vârfului albastru din C se mapează unu-la-unu cu vecinătatea vârfului albastru din H :

Acoperire dublă

În exemplul de mai sus, fiecare vârf al lui H are exact 2 pre-imagini în C. Aici H este o acoperire dublă sau dublă a graficului C .

Pentru orice graf G , se poate construi o acoperire dublă de graf bipartită a lui G care este atât un graf bipartit , cât și o acoperire dublă a lui G în același timp. Acoperirea dublă a graficului bipartit a graficului G este produsul tensor : $G\times K_{2)$

Dacă graficul G este deja bipartit, acoperirea sa dublă bipartită constă din două copii disjunse ale graficului G . Un graf poate avea mai multe acoperiri duble diferite, altele decât acoperirea dublă a unui graf bipartit.

Acoperire universală

Pentru orice graf conex G , se poate construi graficul său universal de acoperire [2] . Acesta este un caz special al conceptului mai general de acoperire universală din topologie. Cerința topologică ca învelișul universal să fie simplu conectat este tradusă în termeni de teoria grafurilor în cerința ca graful să fie conectat și să nu aibă cicluri, adică să fie un arbore . Graficul învelișului universal este unic (până la izomorfism). Dacă un grafic G este un arbore, atunci G însuși este graficul de acoperire universal al lui G. Pentru orice alt grafic conex finit G , graficul de acoperire universal al lui G este un arbore infinit numărabil (dar finit local).

Graficul capacului universal T al unui grafic conectat G poate fi construit după cum urmează. Alegem un vârf arbitrar r al graficului G ca punct de plecare. Fiecare vârf al lui T este o trecere fără întoarcere care începe la r , adică o succesiune de vârfuri în G astfel încât $w=(r,v_{1},v_{2},\dots,v_{n})$

v i și v i +1 sunt adiacente în G pentru tot i , adică w este o trecere
$v_{i-1}\neq v_{i+1}$ pentru tot eu , adică fără întoarcere.

Atunci două vârfuri ale lui T sunt adiacente, dacă unul este o simplă extensie a celuilalt, atunci vârful este adiacent vârfului . Până la izomorfism, același arbore T se obține indiferent de alegerea punctului de plecare r . $(r,v_{1},v_{2},\dots,v_{n})$ $(r,v_{1},v_{2},\dots,v_{n-1})$

Maparea de acoperire f mapează un vârf ( r ) de la T la un vârf r în G și un vârf de la T la un vârf v n în G . $(r,v_{1},v_{2},\dots,v_{n})$

Exemple de huse universale

Următoarea figură ilustrează graficul universal de acoperire T al lui H . Culorile arată afișajul suprapus.

Pentru orice k , toate k -graficele regulate au aceeași acoperire universală, un arbore k -regulat infinit.

Cristal topologic

Un grafic de acoperire abelian cu pliuri infinite a unui (multi)graf finit se numește cristal topologic, o abstractizare a structurii cristaline și este un grafic periodic . De exemplu, un cristal de diamant ca grafic este un grafic de acoperire abelian maxim al unui dipol cu patru margini. Această vedere, combinată cu ideea de „implementații standard”, se dovedește utilă în construcția sistematică a cristalelor (ipotetice) [1] .

Acoperire plană

O acoperire plană a unui graf este o acoperire finită a unui graf de către un graf plan . Proprietatea de a avea o acoperire plană poate fi descrisă de minorii interziși , dar descrierea exactă de acest fel rămâne necunoscută. Orice grafic înglobat în planul proiectiv are o acoperire plană obținută dintr -o acoperire dublă orientabilă planului proiectiv. În 1988, Seiyu Nagami a presupus că numai aceste grafice au acoperiri plane, dar presupunerea rămâne nedovedită [3] .

Grafice de stres

O modalitate generală de a obține grafice de acoperire utilizează grafice de stres în care „săgețile” unui grafic dat G (adică perechi de muchii direcționate corespunzătoare muchiilor nedirecționate ale lui G ) sunt etichetate cu perechi de elemente opuse (adică, un element şi inversul său) dintr-un grup . Graficul obținut din graficul de stres (graf derivat) are ca vârfuri perechi ( v , x ), unde v este un vârf al graficului G , iar x este un element al grupului. Un dart de la v la w etichetat de un element de grup y din G corespunde unei muchii de la ( v , x ) la ( w , xy ) în graficul derivat.

Acoperirea universală poate fi privită în această abordare ca un grafic derivat al graficului de stres, în care marginile arborelui de întindere ale graficului sunt etichetate de elementul de identitate al grupului și fiecare pereche de săgeți rămasă este etichetată de elemente diferite. a grupului liber . Acoperirea dublă bipartită poate fi considerată apoi ca un grafic derivat al graficului de stres, în care fiecare dart este etichetat cu un element de grup diferit de zero de ordinul doi.

Note

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

Literatură

Toshikazu Sunada. Cristalografia topologică -Cu o viziune spre analiza geometrică discretă-. — Springer, 2012.
Petr Hlineny. 20 de ani de conjectura de acoperire plană a lui Negami // Grafice și combinatorie. - 2010. - T. 26 , nr. 4 . — S. 525–536 . - doi : 10.1007/s00373-010-0934-9 .
Chris Godsil, Gordon Royle. Sectă. 6.8 // Teoria graficelor algebrice. — Springer, 2004.
Amit Alon, Nathan Linial, Jiri Matousek, Eyal Rozenman. Random lifts of graphs // Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 7-9 ianuarie (SODA 2001). - 2001. - S. 883-894. — ISBN 0-89871-490-7 .
Dana Angluin. Proprietăți locale și globale în rețelele de procesoare // Proceedings of the 12th annual ACM symposium on Theory of computing (STOC 1980) . - 1980. - ISBN 0-89791-017-6 .