Gráfico de cobertura

Un grafo C es un grafo cubriente de otro grafo G si hay un mapeo cubriente desde el conjunto de vértices C al conjunto de vértices G . El mapeo de cobertura f es una sobreyección y un isomorfismo local: una vecindad de un vértice v en C se mapea biyectivamente a una vecindad de f ( v ) en G .

El término levantamiento se usa a menudo como sinónimo de la cobertura gráfica de un gráfico conexo.

En la teoría de grafos, un gráfico de cobertura también puede referirse a un subgrafo que contiene todos los bordes ( cubierta de borde ) o todos los vértices ( cubierta de vértice ).

La formulación combinatoria de grafos de cobertura se generaliza inmediatamente al caso de multigrafos . Si identificamos un multigrafo con un complejo de celdas unidimensional, el grafo de cobertura no es más que un ejemplo especial de coberturas de espacios topológicos , por lo que se permite la terminología de la teoría de la cobertura, a saber, el grupo de transformación de la cobertura, la cobertura universal. , la cobertura abeliana y la cobertura abeliana máxima [1] .

Definición

Sean y dos gráficas y la función sea sobreyectiva . Entonces f es un mapa que cubre de C a G si, para cada uno, la restricción de f a una vecindad de v es una biyección a una vecindad de f ( v ) en G. En otras palabras, f asigna aristas incidentes a v uno a uno a aristas incidentes a f ( v ). $G=(V_{1},E_{1})$ $C=(V_{2},E_{2})$ $f\dos puntos V_{2}\a V_{1}$ $v\en V_{2}$

Si hay un mapeo de cobertura de C a G , entonces C es un gráfico de cobertura o elevación de G , y G es un gráfico de cociente de C . Un h-lift es un ascensor tal que el mapa de cobertura f tiene la propiedad de que para cualquier vértice v de G , su paquete tiene exactamente h elementos. ${\ estilo de visualización f ^ {-1} (v)}$

Ejemplos

En la siguiente figura, el gráfico C es el gráfico que cubre al gráfico H.

El mapeo de cobertura f de C a H se refleja en colores. Por ejemplo, ambos vértices azules de C se asignan a los vértices azules del gráfico H . El mapeo f es sobreyectivo : cada vértice del gráfico H tiene una preimagen en C. Además, f mapea biyectivamente cada vecino del vértice v del gráfico C a un vecino del vértice f ( v ) del gráfico H.

Por ejemplo, sea v uno de los vértices magenta de C . Tiene dos vecinos en C , un vértice verde u y un vértice azul t . De manera similar, sea v el vértice magenta de H . Tiene dos vecinos en H , un vértice verde u ′ y un vértice azul t ′. La función f restringida a { t , u , v } es una biyección en { t ′, u ′, v ′}. Esto se ilustra en la siguiente figura:

De manera similar, podemos verificar que la vecindad del vértice azul en C se relaciona uno a uno con la vecindad del vértice azul en H :

Cobertura doble

En el ejemplo anterior, cada vértice de H tiene exactamente 2 preimágenes en C . Aquí H es una cubierta doble o cubierta doble del gráfico C.

Para cualquier gráfico G , se puede construir una cubierta de gráfico bipartito doble de G que sea tanto un gráfico bipartito como una cubierta doble de G al mismo tiempo. La doble cobertura del gráfico bipartito del gráfico G es el producto tensorial : ${\displaystyle G\veces K_{2))$

Si el grafo G ya es bipartito, su doble cubierta bipartita consiste en dos copias disjuntas del grafo G. Un gráfico puede tener muchas cubiertas dobles distintas de la cubierta doble de un gráfico bipartito.

Cobertura universal

Para cualquier gráfico conexo G , se puede construir su gráfico de cobertura universal [2] . Este es un caso especial del concepto más general de cobertura universal de la topología. El requisito topológico de que la cubierta universal sea simplemente conexa se traduce en términos de teoría de grafos en el requisito de que el grafo sea conexo y no tenga ciclos, es decir, que sea un árbol . La gráfica de la cobertura universal es única (salvo isomorfismo). Si un grafo G es un árbol, entonces G mismo es el grafo cubriente universal de G. Para cualquier otro grafo conexo finito G , el grafo de cobertura universal de G es un árbol contablemente infinito (pero localmente finito).

El gráfico de la cubierta universal T de un gráfico conexo G se puede construir de la siguiente manera. Elegimos un vértice arbitrario r del gráfico G como punto de partida. Cada vértice de T es un paso sin retorno que comienza en r , es decir, una secuencia de vértices en G tal que $w=(r,v_{1},v_{2},\dots,v_{n})$

v i y v i +1 son adyacentes en G para todo i , es decir, w es un pase
$v_{i-1}\neq v_{i+1}$ para todo i , es decir, no hay retorno.

Entonces dos vértices de T son adyacentes, si uno es una simple extensión del otro, entonces el vértice es adyacente al vértice . Salvo isomorfismo, se obtiene el mismo árbol T independientemente de la elección del punto de partida r . ${\ estilo de visualización (r, v_ {1}, v_ {2}, \ puntos, v_ {n})}$ ${\ estilo de visualización (r, v_ {1}, v_ {2}, \ puntos, v_ {n-1})}$

El mapeo de cobertura f mapea un vértice ( r ) de T a un vértice r en G , y un vértice de T a un vértice v n en G . ${\ estilo de visualización (r, v_ {1}, v_ {2}, \ puntos, v_ {n})}$

Ejemplos de fundas universales

La siguiente figura ilustra el gráfico de cobertura universal T de H . Los colores muestran la pantalla superpuesta.

Para cualquier k , todos los grafos k -regulares tienen la misma cobertura universal, un árbol k -regular infinito.

Cristal topológico

Un gráfico de cobertura abeliano infinitamente plegado de un (multi)gráfico finito se denomina cristal topológico, una abstracción de la estructura cristalina, y es un gráfico periódico . Por ejemplo, un cristal de diamante como gráfico es un gráfico de cobertura abeliana máxima de un dipolo con cuatro aristas. Esta vista, combinada con la idea de "implementaciones estándar", resulta útil en la construcción sistemática de cristales (hipotéticos) [1] .

Revestimiento plano

Una cobertura plana de un gráfico es una cobertura finita de un gráfico por un gráfico plano . La propiedad de tener una cubierta plana puede ser descrita por menores prohibidos , pero se desconoce la descripción exacta de este tipo. Todo grafo incrustado en el plano proyectivo tiene una cubierta plana obtenida a partir de una doble cubierta orientable plano proyectivo. En 1988, Seiyu Nagami conjeturó que solo estos gráficos tienen cubiertas planas, pero la conjetura sigue sin probarse [3] .

Gráficos de tensión

Una forma general de obtener gráficos de cobertura utiliza gráficos de tensión en los que los "dardos" de un gráfico G dado (es decir, pares de aristas dirigidas correspondientes a aristas no dirigidas de G ) se etiquetan con pares de elementos opuestos (es decir, un elemento y su inverso) de algún grupo . La gráfica obtenida a partir de la gráfica de tensiones (gráfica derivada) tiene pares ( v , x ) como vértices, donde v es un vértice de la gráfica G , yx es un elemento del grupo. Un dardo de v a w etiquetado por un elemento de grupo y de G corresponde a un borde de ( v , x ) a ( w , xy ) en el gráfico derivado.

La cobertura universal se puede ver en este enfoque como un gráfico derivado del gráfico de tensión, en el que los bordes del árbol de expansión del gráfico están etiquetados por el elemento de identidad del grupo, y cada par de dardos restante está etiquetado por diferentes elementos. del grupo libre . La doble cubierta bipartita se puede considerar como un gráfico derivado del gráfico de tensión en el que cada dardo está etiquetado con un elemento de grupo distinto de cero de orden dos.

Notas

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

Literatura

Toshikazu Sunada. Cristalografía topológica -con miras al análisis geométrico discreto-. — Springer, 2012.
Petr Hlineny. 20 años de la conjetura de la cubierta plana de Negami // Grafos y Combinatorias. - 2010. - T. 26 , núm. 4 . — S. 525–536 . -doi : 10.1007/ s00373-010-0934-9 .
Chris Godsil, Gordon Royle. Secta. 6.8 // Teoría algebraica de grafos. — Springer, 2004.
Amit Alon, Nathan Linial, Jiri Matousek, Eyal Rozenman. Elevaciones aleatorias de gráficos // Actas del Duodécimo Simposio Anual sobre Algoritmos Discretos, 7-9 de enero (SODA 2001). - 2001. - S. 883-894. — ISBN 0-89871-490-7 .
Dana Angluin. Propiedades locales y globales en redes de procesadores // Actas del duodécimo simposio anual de ACM sobre Teoría de la computación (STOC 1980) . - 1980. - ISBN 0-89791-017-6 .