Un mapa combinatorio es una representación combinatoria de un gráfico en una superficie orientable. Un mapa combinatorio también puede denominarse incrustación combinatoria , sistema de rotación , gráfico de cinta orientable , gráfico de grasa o gráfico cíclico. [1] En términos más generales, un mapa combinatorio -dimensional es una representación combinatoria de un gráfico en una variedad orientable -dimensional.
Los mapas combinatorios se utilizan como estructuras de datos eficientes en la representación y procesamiento de imágenes , en el modelado geométrico. Este modelo está relacionado con los complejos simpliciales y con la topología combinatoria . Un mapa combinatorio es un modelo de representación de límites ; representa un objeto por sus límites.
El concepto de mapa combinatorio fue introducido informalmente por J. Edmonds para superficies poliédricas [2] que son grafos planos . Recibió su primera expresión formal definida bajo el nombre de "Constelaciones" por A. Jacques [3] [4] pero el concepto ya había sido ampliamente utilizado bajo 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 mantuvo y en su lugar se favoreció el de "mapa combinatorio". [6]
Los mapas combinatorios se generalizaron posteriormente para representar objetos subdivididos orientables de dimensiones superiores.
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). En términos más generales, un objeto n-dimensional se compone de celdas de dimensión 0 a n. Además, a menudo también es necesario representar relaciones vecinales entre estas celdas.
De esta forma, queremos describir todas las celdas de la subdivisión, más todas las relaciones de incidencia y adyacencia entre estas celdas. Cuando todas las celdas representadas son símplex, se puede utilizar un complejo simplicial , pero cuando queremos representar cualquier tipo de celdas, necesitamos utilizar modelos topológicos celulares como mapas combinatorios o mapas generalizados.
Un mapa combinatorio es un triplete M = ( D , σ , α ) tal que:
Intuitivamente, un mapa combinatorio corresponde a un grafo en el que cada arista se subdivide en dos dardos (a veces también llamados medias aristas). La permutación σ da, para cada dardo, el siguiente dardo girando alrededor del vértice en la orientación positiva; la otra permutación α da, para cada dardo, el otro dardo de la misma arista.
α permite recuperar aristas ( alpha para rête en francés), y σ permite recuperar vértices ( sigma para s ommet en francés). Definimos φ = σ ∘ α que da, para cada dardo, el siguiente dardo de la misma cara ( phi para f ace también en francés).
Por lo tanto, hay dos formas de representar una función combinatoria según si la permutación es σ o φ (ver el ejemplo a continuación). Estas dos representaciones son duales entre sí: los vértices y las caras se intercambian.
Un mapa combinatorio n -dimensional (o n -mapa) es una ( n + 1)-tupla M = ( D , β 1 , ..., β n ) tal que: [7] [8]
Una función combinatoria n -dimensional representa la subdivisión de un espacio n -dimensional orientable y cerrado. La restricción sobre β i ∘ β j garantiza la validez topológica de la función como subdivisión cuasi-variedad. Las funciones combinatorias bidimensionales se pueden recuperar 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) .
