Hispanopedia Wiki
Articulo de referencia

Mapa combinatorio

Un mapa combinatorio es una representación combinatoria de un grafo en una superficie orientable . Un mapa combinatorio también puede denominarse incrustación combinatoria , sis...

Hispanopedia WikiContenido en espanolLectura gratuita

Un mapa combinatorio es una representación combinatoria de un grafo en una superficie orientable . Un mapa combinatorio también puede denominarse incrustación combinatoria , sistema de rotación , grafo de cinta orientable , grafo gordo o grafo cíclico. [ 1 ] De forma más general, unnorte{\displaystyle n}Un mapa combinatorio de dimensión es una representación combinatoria de un grafo en unnorte{\displaystyle n}-colector dimensional orientable.

Los mapas combinatorios se utilizan como estructuras de datos eficientes en la representación y el procesamiento de imágenes , así como en el modelado geométrico. Este modelo está relacionado con los complejos simpliciales y la topología combinatoria . Un mapa combinatorio es un modelo de representación de límites ; representa un objeto mediante sus límites.

Historia

El concepto de mapa combinatorio fue introducido informalmente por J. Edmonds para superficies poliédricas [ 2 ] , que son grafos planares . Su primera expresión formal definida fue denominada "Constelaciones" por A. Jacques [ 3 ] [ 4 ] , pero el concepto ya había sido ampliamente utilizado con el nombre de "rotación" por Gerhard Ringel [ 5 ] y JWT Youngs en su famosa solución del problema de coloración de mapas de Heawood. El término "constelación" no se conservó y, en su lugar, se prefirió "mapa combinatorio" [ 6 ] .

Posteriormente, los mapas combinatorios se generalizaron para representar objetos subdivididos orientables de dimensiones superiores.

Motivación

Varias aplicaciones requieren una estructura de datos para representar la subdivisión de un objeto. Por ejemplo, un objeto 2D se puede descomponer en vértices (celdas 0), aristas (celdas 1) y caras (celdas 2). De forma más general, un objeto n-dimensional se compone de celdas de dimensión 0 a n. Además, a menudo es necesario representar las relaciones de vecindad entre estas celdas.

Por lo tanto, queremos describir todas las celdas de la subdivisión, así como todas las relaciones de incidencia y adyacencia entre ellas. Cuando todas las celdas representadas son símplexes, se puede utilizar un complejo simplicial ; pero cuando queremos representar cualquier tipo de celda, necesitamos utilizar modelos topológicos celulares como mapas combinatorios o mapas generalizados.

Definición

Un mapa combinatorio es una terna M  =  ( D , σ , α )   tal que:

Intuitivamente, un mapa combinatorio corresponde a un grafo donde cada arista se subdivide en dos puntas (a veces también llamadas medias aristas). La permutación σ proporciona, para cada punta, la siguiente punta girando el vértice en la orientación positiva; la otra permutación α proporciona, para cada punta, la otra punta de la misma arista.

α permite recuperar aristas ( alpha para arête en francés), y σ permite recuperar vértices ( sigma para sommet en francés). Definimos φ  = σ ∘ α  , que da, para cada dardo, el siguiente dardo de la misma cara ( phi para face también en francés).

Así pues, existen dos formas de representar un mapa combinatorio dependiendo de si la permutación es σ o φ (véase el ejemplo a continuación). Estas dos representaciones son duales entre sí: se intercambian vértices y caras.

Generalización de dimensiones superiores

Un mapa combinatorio n -dimensional (o n -mapa) es una tupla ( n  +  1) M  =  ( D , β 1 , ..., β n )    tal que: [ 7 ] [ 8 ]

  • D es un conjunto finito de dardos;
  • β 1 es una permutación en D ;
  • β 2 ,  ..., β n  son involuciones en D ;
  • β i  ∘ β j  es una involución si i  +  2  ≤ j ( i , j ∈ { 1, ,..., n })       .

Un mapa combinatorio n -dimensional representa la subdivisión de un espacio n -dimensional cerrado y orientable. La restricción sobre β i  ∘ β j  garantiza la validez topológica del mapa como una subdivisión de cuasi-variedad. Los mapas combinatorios bidimensionales se pueden obtener fijando n  =  2 y renombrando σ por β 1 y α por β 2 .

Los espacios que no son necesariamente cerrados u orientables pueden representarse utilizando mapas generalizados ( n -dimensionales) .

Sistemas de rotación

En matemáticas combinatorias , los sistemas de rotación (también llamados incrustaciones combinatorias o mapas combinatorios ) codifican incrustaciones de grafos en superficies orientables describiendo el orden circular de las aristas de un grafo alrededor de cada vértice. Una definición más formal de un sistema de rotación implica pares de permutaciones ; dicho par es suficiente para determinar un multigrafo , una superficie y una incrustación de dos celdas del multigrafo sobre la superficie.

Cada esquema de rotación define una incrustación única de 2 celdas de un multigrafo conexo sobre una superficie cerrada orientada (salvo equivalencia topológica que preserve la orientación). A la inversa, cualquier incrustación de un multigrafo conexo G sobre una superficie cerrada orientada define un sistema de rotación único que tiene a G como su multigrafo subyacente. Esta equivalencia fundamental entre sistemas de rotación e incrustaciones de 2 celdas fue establecida por primera vez en forma dual por Lothar Heffter en la década de 1890 [ 9 ] y ampliamente utilizada por Ringel durante la década de 1950 [ 10 ] . De forma independiente, Edmonds dio la forma primal del teorema [ 11 ] y los detalles de su estudio han sido popularizados por Youngs [ 12 ] . La generalización a multigrafos fue presentada por Gross y Alpert [ 13 ] .

Los sistemas de rotación están relacionados con los mapas de rotación utilizados por Reingold et al. (2002) para definir el producto en zigzag de grafos, pero no son lo mismo. Un sistema de rotación especifica un ordenamiento circular de las aristas alrededor de cada vértice, mientras que un mapa de rotación especifica una permutación (no circular) de las aristas en cada vértice. Además, los sistemas de rotación pueden definirse para cualquier grafo, mientras que, tal como los definen Reingold et al., los mapas de rotación se limitan a grafos regulares .

Caracterización de la superficie de la incrustación

Según la fórmula de Euler podemos deducir el género g de la superficie orientable cerrada definida por el sistema de rotación.(σ,θ){\displaystyle (\sigma ,\theta )}(es decir, la superficie sobre la que el multigrafo subyacente está incrustado en 2 celdas). [ 14 ] Nótese queV=|Z(σ)|{\displaystyle V=|Z(\sigma)|},mi=|Z(θ)|{\displaystyle E=|Z(\theta)|}yF=|Z(σθ)|{\displaystyle F=|Z(\sigma \theta )|}. Encontramos que

gramo=1−12(V−mi+F)=1−12(|Z(σ)|−|Z(θ)|+|Z(σθ)|){\displaystyle g=1-{\frac {1}{2}}(V-E+F)=1-{\frac {1}{2}}(|Z(\sigma )|-|Z(\theta )|+|Z(\sigma \theta )|)}

dóndeZ(ϕ){\displaystyle Z(\phi )}denota el conjunto de las órbitas de permutaciónϕ{\displaystyle \phi }.

Véase también

Referencias

  1. ↑ Bollobás, Béla; Riordan, Oliver (2001). "Un invariante polinomial de grafos en superficies orientables". Actas de la Sociedad Matemática de Londres . 83 (3). Wiley: 513– 531. doi : 10.1112/plms/83.3.513 . ISSN 0024-6115 . S2CID 15895860 .  
  2. ↑ Edmonds, J. (1960). "Una representación combinatoria para superficies poliédricas". Notices Amer. Math. Soc . 7. hdl : 1903/24820 .
  3. ^ Jacques, A. (1969). Constelaciones y propiedades algébriques des graphes topologiques (PhD). Universidad de París.
  4. ^ Jacques, A. (1970). "Constelaciones y gráficos topológicos". Coloque de Matemáticas. Soc. János Bolyai : 657–672 .
  5. ^ Ringel, G. (2012) [1974]. Teorema del color del mapa . Saltador. ISBN 978-3-642-65759-7.
  6. ^ Cori, R. (1975). "Un código para los gráficos planos y sus aplicaciones" . Astérisque . 27 . SEÑOR 0404045 . Zbl 0313.05115 .  
  7. ↑ Lienhardt, P. (1991). "Modelos topológicos para la representación de límites : una comparación con mapas generalizados n-dimensionales". Computer-Aided Design . 23 (1): 59– 82. doi : 10.1016/0010-4485(91)90082-8 . 
  8. ↑ Lienhardt, P. (1994). "Mapas combinatorios generalizados N-dimensionales y cuasi-variedades celulares". International Journal of Computational Geometry and Applications . 4 (3): 275– 324. doi : 10.1142/S0218195994000173 .
  9. ↑ Heffter (1891) , Heffter (1898)
  10. ↑ Ringel (1965)
  11. ↑ Edmonds (1960a) , Edmonds (1960b)
  12. ↑ Youngs (1963)
  13. ↑ Gross y Alpert (1974)
  14. ↑ Lando y Zvonkin (2004) , fórmula 1.3, pág. 38.

Bibliografía

  • Cori, R.; Machì, A. (1992). "Mapas, hipermapas y sus automorfismos: una encuesta". Exposiciones Mathematicae . 10 : 403– 467. SEÑOR 1190182 . 
  • Edmonds, J. (1960a). "Una representación combinatoria para superficies poliédricas". Notices of the American Mathematical Society . 7 : 646.
  • Edmonds, John Robert (1960b). Una representación combinatoria para superficies poliédricas orientadas (PDF) (Maestría). Universidad de Maryland. hdl : 1903/24820 .
  • Gross, JL; Alpert, SR (1974). "La teoría topológica de los grafos de corriente" . Journal of Combinatorial Theory, Serie B. 17 ( 3): 218– 233. doi : 10.1016/0095-8956(74)90028-8 . MR 0363971 . 
  • Heffter, L. (1891). "Über das Problem der Nachbargebiete" . Annalen Matemáticas . 38 (4): 477– 508. doi : 10.1007/BF01203357 . S2CID 121206491 . 
  • Heffter, L. (1898). "Über metacyklische Gruppen und Nachbarcontigurationen" . Annalen Matemáticas . 50 ( 2– 3): 261– 268. doi : 10.1007/BF01448067 . S2CID 120691296 . 
  • Lando, Sergei K.; Zvonkin, Alexander K. (2004). Grafos en superficies y sus aplicaciones . Enciclopedia de ciencias matemáticas: Topología de dimensiones inferiores II. Vol.  141. Springer-Verlag . ISBN 978-3-540-00203-1..
  • Mohar, Bojan ; Thomassen, Carsten (2001). Grafos en superficies . Johns Hopkins University Press. ISBN 0-8018-6689-8.
  • Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Ondas de entropía, el producto de grafos en zigzag y nuevos expansores de grado constante". Annals of Mathematics . 155 (1): 157– 187. arXiv : math/0406038 . doi : 10.2307/3062153 . JSTOR 3062153. MR 1888797. S2CID 120739405 .   
  • Ringel, G. (1965). "Das Geschlecht des vollständigen paaren Graphen". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 28 ( 3– 4): 139– 150. doi : 10.1007/BF02993245 . SEÑOR 0189012 . S2CID 120414651 .  
  • Youngs, JWT (1963). "Incrustaciones mínimas y el género de un grafo" . Journal of Mathematics and Mechanics . 12 (2): 303– 315. doi : 10.1512/iumj.1963.12.12021 . MR 0145512 . 
  • Mapas combinatorios en CGAL , la biblioteca de algoritmos de geometría computacional:
    • Damiand, Guillaume. "Mapas combinatorios" . Consultado el 6 de febrero de 2021 .
  • Mapas combinatorios en CGoGN , modelado combinatorio y geométrico con mapas genéricos N - dimensionales
  • Mapa combinatorio en el Laboratorio n