En la disciplina matemática de la teoría de grafos, un grafo es un grafo de recubrimiento de otro grafo si existe una aplicación de recubrimiento del conjunto de vértices de sobre el conjunto de vértices de . Una aplicación de recubrimiento es una función sobreyectiva y un isomorfismo local: la vecindad de un vértice en se hace corresponder biyectivamente sobre la vecindad de en .

El término elevación se utiliza a menudo como sinónimo de grafo de recubrimiento de un grafo conexo.

Aunque pueda ser engañoso, no existe una relación (obvia) entre el grafo de recubrimiento y la cobertura de vértices o la cobertura de aristas.

La formulación combinatoria de grafos de recubrimiento se generaliza inmediatamente al caso de los multigrafos. Un grafo de recubrimiento es un caso especial de un complejo de recubrimiento. Tanto los complejos de recubrimiento como los multigrafos con un complejo celular unidimensional son ejemplos de espacios recubridores de espacios topológicos, por lo que la terminología de la teoría de espacios de recubrimiento está disponible, como por ejemplo, el grupo de transformación de cubrimiento, el cubrimiento universal, el cubrimiento abeliano y el cubrimiento abeliano máximo.

Definición

Sean G = (V1, E1) y C = (V2, E2) dos grafos, y sea f: V2 → V1 una función sobreyectiva. Entonces f es una función de cubrimiento de C sobre G si para cada v ∈ V2, la restricción de f a la vecindad de v es una biyección sobre la vecindad de f(v) en G. Dicho de otro modo, f hace corresponder las aristas incidentes a v biunívocamente con las aristas incidentes en f(v).

Si existe una función de recubrimiento de C sobre G, entonces C es un grafo de recubrimiento, o una elevación, de G. Una h-elevación es una elevación tal que la función de recubrimiento f tiene la propiedad de que, para cada vértice v de G, su fibra f−1(v) tiene exactamente h elementos.

Ejemplos

En la siguiente figura, el grafo C es un grafo de recubrimiento del grafo H.

La función de recubrimiento f de C sobre H se indica con los colores. Por ejemplo, ambos vértices azules de C se aplican 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 hace corresponder 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 forma 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 forma similar, se puede comprobar que la vecindad de un vértice azul en C se corresponde biunívocamente sobre la vecindad del vértice azul en H:

Doble cobertura

En el ejemplo anterior, cada vértice de H tiene exactamente dos preimágenes en C. Por lo tanto, C es un doble recubrimiento o una doble cobertura de H.

Para cualquier grafo G, es posible construir el doble cubrimiento bipartito de G, que es un grafo bipartito y una doble cobertura de G. El doble cubrimiento bipartito de G es producto tensorial de grafos G × K2:

Si G ya es bipartito, su doble cobrimiento bipartito consiste en dos copias disjuntas de G. Un grafo puede tener muchos dobles cubrimientos diferentes además del doble cubrimiento bipartito.

Recubrimiento universal

Para cualquier grafo conexo G, es posible construir su grafo de recubrimiento universal. Este es un ejemplo del concepto más general de espacio recubridor de la topología: el requisito topológico de que un recubrimiento universal sea un conjunto simplemente conexo se traduce, en términos de teoría de grafos, en el requisito de que sea acíclico y conexo, es decir, un árbol. El grafo de recubrimiento universal es único (salvo isomorfismos). Si G es un árbol, entonces G es el propio grafo recubridor universal de G. Para cualquier otro grafo conexo finito G, el grafo recubridor universal de G es un árbol numerablemente infinito (pero localmente finito).

El grafo de recubrimiento universal T de un grafo conexo G se puede construir de la siguiente manera: elegir un vértice arbitrario r de G como punto de partida. Cada vértice de T es un recorrido sin retroceso que comienza en r, es decir, una secuencia w = (r, v1, v2, ..., vn) de vértices de G tales que

vi y vi+1 son adyacentes en G para todo i, es decir, w es un recorrido. vi-1 ≠ vi+1 para todo i, es decir, w no es un recorrido sin retroceso.

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). Prescindiendo de isomorfismos, el mismo árbol T se construye independientemente del punto de partida r.

La función de recubrimiento f asigna el vértice (r) de T al vértice r de G, y un vértice (r, v1, v2, ..., vn) de T al vértice vn de G.

Ejemplos de recubrimientos universales

La siguiente figura ilustra el grafo de recubrimiento universal T de un grafo H; los colores indican el mapa de recubrimiento.

Para cualquier k, todos los k-grafos regulares tienen el mismo recubrimiento universal: el árbol regular k infinito.

Cristal topológico

Un grafo de recubrimiento abeliano de infinitos lóbulos 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 dipolo de cuatro aristas. Esta perspectiva, combinada con la idea de realizaciones estándar, resulta útil en el diseño sistemático de cristales (hipotéticos).

Recubrimiento plano

Un recubrimiento plano de un grafo es un grafo de recubrimiento finito que es en sí mismo un grafo plano. La propiedad de tener una cobertura plana puede caracterizarse mediante menores prohibidos, pero la caracterización exacta de esta forma se desconoce. Todo grafo con un embebido en el plano proyectivo tiene una cobertura plana proveniente de la orientabilidad del plano proyectivo. En 1988, Seiya Nagami conjeturó que estos son los únicos grafos con coberturas planas, pero esto aún no se ha demostrado..

Grafos de voltaje Una forma común de formar grafos de cobertura utiliza grafos de voltaje, en los que las flechas del grafo dado G (es decir, pares de aristas dirigidas correspondientes a las aristas no dirigidas de G) se etiquetan 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 del grupo. Un enlace orientado 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 cobertura universal puede verse así como un grafo derivado de un grafo de voltaje en el que las aristas de un árbol de expansión del grafo están etiquetadas por el elemento identidad del grupo, y cada par de enlaces orientados restante está etiquetado por un elemento generador distinto de un grupo libre. El doble bipartito puede verse así como un grafo derivado de un grafo de voltaje en el que cada enlace orientado está etiquetado por el elemento distinto de cero del grupo de orden dos.

Referencias

Bibliografía

Categoría:Grafos Categoría:Problemas de recubrimiento