Ordenación de bordes
Introducción
En matemáticas combinatorias, un sistema de rotación (también llamado incrustación o embebido combinatorio) sirve para codificar grafos embebidos en superficies "Superficie (topología)") orientables, describiendo la ordenación circular") de los bordes de un grafo alrededor de cada vértice.
Una definición más formal de un sistema de rotación implica pares de permutaciones. Dichos pares son suficientes para determinar un multigrafo, una superficie y un embebido de dos celdas del multigrafo sobre la superficie.
Cada esquema de rotación define una incrustación única de dos celdas de un multigrafo conectado "Conectividad (teoría de grafos)") en una superficie orientada cerrada (hasta la equivalencia topológica que conserva la orientación). Por el contrario, cualquier incrustación de un multigrafo conectado G en una superficie cerrada orientada define un sistema de rotación único que tiene G como su multigrafo subyacente. Esta equivalencia fundamental entre los sistemas de rotación y los embebidos de dos celdas fue establecida por primera vez de forma dual por Lothar Heffter en la década de 1890[1] y utilizada ampliamente por Ringel durante la década de 1950.[2] Independientemente, Edmonds dio la forma original del teorema[3] y los detalles de su estudio han sido popularizados por Youngs.[4] La generalización a multigrafos fue presentada por Gross y Alpert.[5].
Los sistemas de rotación están relacionados, pero no son los mismos, con los mapas de rotación") utilizados por Reingold et al. (2002) para definir el producto en zig-zag") de grafos. Un sistema de rotación especifica una ordenación circular de los bordes alrededor de cada vértice, mientras que un mapa de rotación especifica una permutación (no circular) de los bordes en cada vértice. Además, los sistemas de rotación se pueden definir para cualquier grafo, mientras que los mapas de rotación definidos según Reingold et al. están restringidos a grafos regulares.
Definición formal
Formalmente, un sistema de rotación se define como un par (σ, θ) donde σ y θ son permutaciones que actúan sobre el mismo conjunto base B, θ es un punto fijo libre de involución "Involución (matemática)"), y el grupo "Grupo (matemática)") <σ, θ> generado por las acciones "Acción (matemática)") σ y θ transitivamente "Acción (matemática)") en .