En matemáticas , un mapa de rotación es una función que representa un gráfico marcado por bordes no dirigido , donde cada vértice enumera sus vecinos salientes. Los mapas de rotación fueron introducidos por primera vez por Reingold, Vadhan y Wigderson ("Ondas de entropía, el producto gráfico en zig-zag y nuevos expansores de grado constante", 2002) para definir convenientemente el producto en zig-zag y probar sus propiedades. Dado un vértice y una etiqueta de borde , el mapa de rotación devuelve el 'el vecino de y la etiqueta de borde que volvería a .
Definición
Para un gráfico D -regular G , el mapa de rotación se define de la siguiente manera: si el i- ésimo borde que deja v conduce a w , y el j- ésimo borde que deja w conduce a v .
Propiedades básicas
De la definición vemos que es una permutación, y además es el mapa de identidades una involución ).
Casos y propiedades especiales
- Un mapa de rotación se etiqueta consistentemente si todos los bordes que salen de cada vértice están etiquetados de tal manera que en cada vértice, las etiquetas de los bordes entrantes son todas distintas. Cada gráfico regular tiene un etiquetado coherente.
- Un mapa de rotación es -consistente si . De la definición, un-El mapa de rotación consistente está etiquetado de manera consistente.
Ver también
Referencias
- Reingold, O .; Vadhan, S .; Widgerson, A. (2000), "Ondas de entropía, el producto gráfico en zig-zag y nuevos expansores y extractores de grado constante", 41º Simposio anual sobre los fundamentos de la informática : 3–13, arXiv : math / 0406038 , doi : 10.1109 / SFCS.2000.892006 , ISBN 978-0-7695-0850-4
- Reingold, O (2008), "Conectividad no dirigida en el espacio de registro", Journal of the ACM , 55 (4): 1–24, doi : 10.1145 / 1391289.1391291
- Reingold, O .; Trevisan, L .; Vadhan, S. (2006), "Pseudoaleatorio camina sobre dígrafos regulares y el problema RL vs. L", Actas del Trigésimo octavo Simposio Anual ACM sobre Teoría de la Computación : 457, doi : 10.1145 / 1132516.1132583 , ISBN 978-1595931344
- Alexander, C. (2021), A Note on Consistent Rotation Maps of Graph Cartesian Products , doi : 10.13140 / RG.2.2.19721.57446