En la disciplina matemática de la teoría de grafos , un grafo C es un grafo cubriente de otro grafo G si existe una función cubriente desde el conjunto de vértices de C al conjunto de vértices de G. Una función cubriente f es una sobreyección y un isomorfismo local : el vecindario de un vértice v en C se mapea biyectivamente sobre el vecindario de en G.
El término elevación se utiliza a menudo como sinónimo de un gráfico de cobertura de un gráfico conexo .
Aunque pueda 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 aristas .
La formulación combinatoria de los grafos de recubrimiento se generaliza inmediatamente al caso de los multigrafos . Un grafo de recubrimiento es un caso especial de un complejo de recubrimiento. [1] Tanto los complejos de recubrimiento como los multigrafos con un complejo de celdas unidimensional no son más que ejemplos de espacios de recubrimiento de espacios topológicos , por lo que la terminología en la teoría de espacios de recubrimiento está disponible; digamos grupo de transformación de recubrimiento, recubrimiento universal, recubrimiento abeliano y recubrimiento abeliano máximo. [2]
Sean G = ( V 1 , E 1 ) y C = ( V 2 , E 2 ) dos grafos, y sea f : V 2 → V 1 una sobreyección . Entonces f es una función de recubrimiento de C a G si para cada v ∈ V 2 , la restricción de f al entorno de v es una biyección sobre el entorno de f ( v ) en G . Dicho de otro modo, f aplica las aristas incidentes a v biyectivamente sobre las aristas incidentes a f ( v ).
Si existe un mapa de recubrimiento de C a G , entonces C es un grafo de recubrimiento , o un ascensor , de G . Un h-ascensor es un ascensor tal que el mapa de recubrimiento 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 de cobertura del gráfico H.
La función de recubrimiento f de C a H se indica con los colores. Por ejemplo, ambos vértices azules de C se asignan al vértice azul de H. La función f es una sobreyección: cada vértice de H tiene una preimagen en C. Además, f asigna biyectivamente cada entorno de un vértice v en C sobre el entorno del vértice f ( v ) en H.
Por ejemplo, sea v uno de los vértices morados 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 morado de 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 lo tanto, C es una cubierta doble o una cubierta doble de H.
Para cualquier grafo G , es posible construir la doble cobertura bipartita de G , que es un grafo bipartito y una doble cobertura de G . La doble cobertura bipartita de G es el producto tensorial de los grafos G × K 2 :
Si G ya es bipartito, su doble cobertura bipartita consta de dos copias disjuntas de G. Un grafo puede tener muchas dobles coberturas diferentes además de la doble cobertura bipartita.
Para cualquier grafo conexo G , es posible construir su grafo de recubrimiento universal . [3] Este es un ejemplo del concepto de recubrimiento universal más general de la topología; el requisito topológico de que un recubrimiento universal sea simplemente conexo se traduce en términos de teoría de grafos a un requisito de que sea acíclico y conexo; es decir, un árbol . El grafo de recubrimiento universal es único (salvo isomorfismo). Si G es un árbol, entonces G mismo es el grafo de recubrimiento universal de G . Para cualquier otro grafo conexo finito G , el grafo de recubrimiento universal de G es un árbol numerablemente infinito (pero localmente finito).
El grafo universal T de recubrimiento de un grafo 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 tales que
Entonces, dos vértices de T son adyacentes si uno es una extensión simple de otro: el vértice ( r , v1 , v2 , ..., vn ) es adyacente al vértice ( r , v1 , v2 , ..., vn - 1 ). Hasta el isomorfismo, se construye el mismo árbol T independientemente de la elección del punto de partida r .
La función 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 - grafos regulares tienen la misma cobertura universal: el árbol k -regular infinito.
Un grafo de recubrimiento abeliano de pliegue infinito de un (multi)grafo finito se denomina cristal topológico, una abstracción de las estructuras cristalinas. Por ejemplo, el cristal de diamante como grafo es el grafo de recubrimiento abeliano máximo del grafo dipolar de cuatro aristas . Esta visión combinada con la idea de "realizaciones estándar" resulta útil en un diseño sistemático de cristales (hipotéticos). [2]
Una cubierta plana de un grafo es un grafo de cubierta finito que es en sí mismo un grafo plano . La propiedad de tener una cubierta plana puede caracterizarse por menores prohibidos , pero la caracterización exacta de esta forma sigue siendo desconocida. Todo grafo con una incrustación en el plano proyectivo tiene una cubierta plana que proviene de la doble cubierta orientable del plano proyectivo; en 1988, Seiya Nagami conjeturó que estos son los únicos grafos con cubiertas planas, pero esto sigue sin demostrarse. [4]
Una forma común de formar grafos de recubrimiento utiliza grafos de voltaje , en los que los dardos del grafo 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 . El grafo derivado del grafo de voltaje tiene como vértices los pares ( v , x ) donde v es un vértice de G y x es un elemento de grupo; un dardo de v a w etiquetado con el elemento de grupo y en G corresponde a una arista de ( v , x ) a ( w , xy ) en el grafo derivado.
La cubierta 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 identidad del grupo, y cada par restante de dardos está etiquetado por un elemento generador distinto de un grupo libre . El doble bipartito puede verse de esta manera como un gráfico derivado de un gráfico de voltaje en el que cada dardo está etiquetado por el elemento distinto de cero del grupo de orden dos.
