Grafo de recobriment
En la disciplina matemàtica de la teoria de grafos, un grafo C és un grafo de recobriment d'un atre grafo G si existix una aplicació de recobriment del conjunt de vèrtiços de C sobre el conjunt de vèrtiços de G. Una aplicació de recobriment f és una funció sobreyectiva i un isomorfisme local: la veïnat d'un vèrtiç v en C es fa correspondre biyectivamente sobre el veïnat de Plantilla:Tmath en G.
El terme elevació s'utilisa a sovint com a sinònim de grafo de recobriment d'un grafo conexo.
Encara que puga ser enganyós, no existix una relació (òbvia) entre el grafo de recobriment i la cobertura de vèrtiços o la cobertura d'arestes.
La formulació combinatòria de grafos de recobriment es generalisa immediatament al cas dels multigrafos. Un grafo de recobriment és un cas especial d'un complex de recobriment.[1] Tant els complexos de recobriment com els multigrafos en un complex celular unidimensional són eixemples d'espais recubridores d'espais topològics, per lo que la terminologia de la teoria d'espais de recobriment està disponible, com per eixemple, el grup de transformació de cubrimiento, el cubrimiento universal, el cubrimiento abeliano i el cubrimiento abeliano màxim.
Definició
Siguen G = (V1, I1) i C = (V2, I2) dos grafos, i siga f: V2 → V1 una funció sobreyectiva. Llavors f és una funció de cubrimiento de C sobre G si per a cada v ∈ V2, la restricció de f a la veïnat de v és una biyección sobre el veïnat de f(v) en G. Dit d'un atre modo, f fa correspondre les arestes incidents a v biunívocament en les arestes incidents en f(v).
Si existix una funció de recobriment de C sobre G, llavors C és un grafo de recobriment, o una elevació, de G. Una h-elevació és una elevació tal que la funció de recobriment f té la propietat de que, per a cada vèrtiç v de G, la seua fibra f−1(v) té exactament h elements.
Eixemples
En la següent figura, el grafo C és un grafo de recobriment del grafo H.
La funció de recobriment f de C sobre H s'indica en els colors. Per eixemple, abdós vèrtiços blaus de C s'apliquen al vèrtiç blau de H. La funció f és una sobreyección: cada vèrtiç de H té una preimagen en C. Ademés, f fa correspondre biyectivamente cada veïnat d'un vèrtiç v en C al veïnat del vèrtiç f(v) en H.
Per eixemple, siga v un dels vèrtiços morats en C; té dos veïns en C, un vèrtiç vert o i un vèrtiç blau t. De forma similar, siga v′ el vèrtiç morat en H; té dos veïns en H, el vèrtiç vert o′ i el vèrtiç blau t′. L'aplicació f restringida a t, o, v és una biyección sobre t′, o′, v′. Açò s'ilustra en la següent figura:
De forma similar, es pot comprovar que el veïnat d'un vèrtiç blau en C es correspon biunívocament sobre el veïnat del vèrtiç blau en H:
Referències
- ↑ Rotman, Joseph(més de Decembre de 1973).«Covering complexes with applications to algebra».Rocky Mountain Journal of Mathematics.3(4): 641–674.doi:10.1216/RMJ-1973-3-4-641.
Bibliografia
- Godsil, Chris; Royle, Gordon F. (2001). «§6.8 Foldings and Covers», Algebraic Graph Theory (vol. 207), Springer, pp. 114–6. ISBN 978-0-387-95220-8.
- Amit, Alon; Linial, Nathan; Matoušek, Jiří; Rozenman, Eyal (2001). «Random lifts of graphs», Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms (SODA '01), Society for Industrial and Applied Mathematics, pp. 883–894. ISBN 978-0-89871-490-6. «citeseerx: 10.1.1.719.3508»
- Angluin, Dana (1980). «Local and global properties in networks of processors (Estendre Abstract)», Proceedings of the twelfth annual ACM symposium on Theory of computing (STOC '80), Association for Computing Machinery, pp. 82–93. doi:10.1145/800141.804655. ISBN 978-0-89791-017-0.
Referències
- Este artícul conté una traducció derivada de «Grafo de recubrimiento» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.