En la disciplina matemática de la teoría de grafos , un gráfico C es un gráfico de cobertura de otro gráfico G si hay un mapa de cobertura desde el conjunto de vértices de C hasta el conjunto de vértices de G. Un mapa de cobertura f es una sobreyección y un isomorfismo local : la vecindad de un vértice v en C se asigna biyectivamente a la vecindad de en G.
El término elevación se utiliza a menudo como sinónimo de gráfico de cobertura de un gráfico conectado .
Aunque puede resultar engañoso, no existe una relación (obvia) entre el gráfico de cobertura y la cobertura de vértices o la cobertura de bordes .
La formulación combinatoria de grafos de cobertura se generaliza inmediatamente al caso de multigrafos . Un gráfico de cobertura es un caso especial de complejo de cobertura. [1] Tanto los complejos de cobertura como los multigrafos con un complejo de celdas unidimensionales no son más que ejemplos de espacios de cobertura de espacios topológicos , por lo que la terminología en la teoría de espacios de cobertura está disponible; digamos grupo de transformación de cobertura, cobertura universal, cobertura abeliana y cobertura abeliana máxima. [2]
Sean G = ( V 1 , E 1 ) y C = ( V 2 , E 2 ) dos gráficas, y sea f : V 2 → V 1 una sobreyección . Entonces f es un mapa de cobertura de C a G si para cada v ∈ V 2 , la restricción de f a la vecindad de v es una biyección sobre la vecindad de f ( v ) en G . Dicho de otra manera, f asigna los bordes incidentes a v uno a uno sobre los bordes incidentes a f ( v ).
Si existe un mapa de cobertura de C a G , entonces C es un gráfico de cobertura , o una elevación , de G. Un levantamiento h es un levantamiento tal que el mapa de cobertura f tiene la propiedad de que para cada vértice v de G , su fibra f −1 (v) tiene exactamente h elementos.
En la siguiente figura, el gráfico C es un gráfico que cubre el gráfico H.
El mapa de cobertura f de C a H está indicado con colores. Por ejemplo, ambos vértices azules de C se asignan al vértice azul de H. El mapa f es una sobreyección: cada vértice de H tiene una preimagen en C . Además, f asigna biyectivamente cada vecindad de un vértice v en C a la vecindad del vértice f ( v ) en H.
Por ejemplo, sea v uno de los vértices morados en 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 morado en H ; tiene dos vecinos en H , el vértice verde u ′ y el vértice azul t ′ . La aplicación f restringida a { t , u , v } es una biyección sobre { t ′ , u ′ , v ′ }. Esto se ilustra en la siguiente figura:
De manera similar, podemos comprobar que la vecindad de un vértice azul en C se asigna uno a uno a la vecindad del vértice azul en H :
En el ejemplo anterior, cada vértice de H tiene exactamente 2 preimágenes en C. Por tanto, C es una cubierta doble o una cubierta doble de H.
Para cualquier gráfico G , es posible construir la doble cobertura bipartita de G , que es un gráfico bipartito y una doble cobertura de G. La doble cobertura bipartita de G es el producto tensorial de los gráficos G × K 2 :
Si G ya es bipartito, su doble cubierta bipartita consta de dos copias disjuntas de G . Un gráfico puede tener muchas coberturas dobles diferentes además de la doble cobertura bipartita.
Para cualquier gráfico conexo G , es posible construir su gráfico de cobertura universal . [3] Este es un ejemplo del concepto de cobertura universal más general de la topología; el requisito topológico de que una cobertura universal sea simplemente conexa se traduce en términos de teoría de grafos al requisito de que sea acíclica y conexa; es decir, un árbol . El gráfico de cobertura universal es único (hasta el isomorfismo). Si G es un árbol, entonces G en sí es el gráfico de cobertura universal de G. Para cualquier otro gráfico finito conectado G , el gráfico de cobertura universal de G es un árbol contablemente infinito (pero localmente finito).
El gráfico de cobertura universal T de un gráfico conexo G se puede construir de la siguiente manera. Elija un vértice arbitrario r de G como punto de partida. Cada vértice de T es un recorrido sin retroceso que comienza desde r , es decir, una secuencia w = ( r , v 1 , v 2 , ..., v n ) de vértices de G tal que
Entonces, dos vértices de T son adyacentes si uno es una simple extensión de otro: el vértice ( r , v 1 , v 2 , ..., v n ) es adyacente al vértice ( r , v 1 , v 2 , . .., vn - 1 ). Hasta el isomorfismo, se construye el mismo árbol T independientemente de la elección del punto de partida r .
El mapa de cobertura f asigna el vértice ( r ) en T al vértice r en G , y un vértice ( r , v 1 , v 2 , ..., v n ) en T al vértice v n en G.
La siguiente figura ilustra el gráfico de cobertura universal T de un gráfico H ; los colores indican el mapa de cobertura.
Para cualquier k , todos los k - gráficos regulares tienen la misma cobertura universal: el infinito k -árbol regular.
Un gráfico de cobertura abeliano de pliegues infinitos de un (multi)gráfico finito se llama cristal topológico, una abstracción de estructuras cristalinas. Por ejemplo, el cristal de diamante como gráfico es el gráfico de cobertura abeliano máximo del gráfico dipolo de cuatro aristas . Este punto de vista combinado con la idea de "realizaciones estándar" resulta útil en un diseño sistemático de cristales (hipotéticos). [2]
Una cobertura plana de un gráfico es un gráfico de cobertura finita que es en sí mismo un gráfico plano . La propiedad de tener una cubierta plana puede caracterizarse por menores prohibidos , pero se desconoce la caracterización exacta de esta forma. Todo grafo con incrustación en el plano proyectivo tiene una cubierta plana proveniente de la doble cubierta orientable del plano proyectivo; En 1988, Seiya Nagami conjeturó que estos son los únicos gráficos con cubiertas planas, pero esto aún no se ha demostrado. [4]
Una forma común de formar gráficos de cobertura utiliza gráficos de voltaje , en los que los dardos del gráfico dado G (es decir, pares de aristas dirigidas correspondientes a las aristas no dirigidas de G ) están etiquetados con pares inversos de elementos de algún grupo . La gráfica derivada de la gráfica de voltaje tiene como vértices los pares ( v , x ) donde v es un vértice de G y x es un elemento del grupo; un dardo de v a w etiquetado con el elemento de grupo y en G corresponde a un borde de ( v , x ) a ( w , xy ) en el gráfico derivado.
La cobertura universal puede verse de esta manera como un gráfico derivado de un gráfico de voltaje en el que los bordes de un árbol de expansión del gráfico están etiquetados por el elemento de identidad del grupo, y cada par de dardos restantes está etiquetado por un elemento generador distinto. elemento de un grupo libre . El doble bipartito puede verse de esta manera como una gráfica derivada de una gráfica de voltaje en la que cada dardo está etiquetado por el elemento distinto de cero del grupo de orden dos.
