En teoría de grafos , la escalera de Möbius M n , para números pares n , se forma a partir de un ciclo n mediante la adición de aristas (llamadas "peldaños") que conectan pares opuestos de vértices en el ciclo. Es un grafo cúbico , circulante , llamado así porque (con la excepción de M 6 (el grafo de utilidad K 3,3 ), M n tiene exactamente n /2 cuatriciclos [1] que se unen entre sí por sus aristas compartidas para formar una banda de Möbius topológica . Las escaleras de Möbius fueron nombradas y estudiadas por primera vez por Guy y Harary (1967).
Para cada par n > 4 , la escalera de Möbius M n es un grafo de vértice no plano , lo que significa que no se puede dibujar sin cruces en el plano, pero la eliminación de un vértice permite dibujar el grafo restante sin cruces. Estos grafos tienen el cruce número uno y se pueden incrustar sin cruces en un toro o plano proyectivo . Por lo tanto, son ejemplos de grafos toroidales . Li (2005) explora las incrustaciones de estos grafos en superficies de género superior.
Las escaleras de Möbius son transitivas de vértice – tienen simetrías que llevan cualquier vértice a cualquier otro vértice – pero (con las excepciones de M 4 y M 6 ) no son transitivas de arista . Las aristas del ciclo a partir del cual se forma la escalera se pueden distinguir de los peldaños de la escalera, porque cada arista de ciclo pertenece a un solo 4-ciclo, mientras que cada peldaño pertenece a dos de esos ciclos. Por lo tanto, no hay simetría que lleve una arista de ciclo a una arista de peldaño o viceversa.
Cuando n ≡ 2 (mod 4) , M n es bipartito . Cuando n ≡ 0 (mod 4) , no es bipartito. Los puntos finales de cada peldaño están separados por una distancia par en el ciclo inicial, por lo que al sumar cada peldaño se crea un ciclo impar. En este caso, debido a que el grafo es 3-regular pero no bipartito, por el teorema de Brooks tiene número cromático 3. De Mier y Noy (2004) muestran que las escaleras de Möbius están determinadas de forma única por sus polinomios de Tutte .
La escalera de Möbius M 8 tiene 392 árboles de expansión ; esta y M 6 tienen la mayor cantidad de árboles de expansión entre todos los grafos cúbicos con el mismo número de vértices. [2] Sin embargo, el grafo cúbico de 10 vértices con la mayor cantidad de árboles de expansión es el grafo de Petersen , que no es una escalera de Möbius.
Los polinomios de Tutte de las escaleras de Möbius se pueden calcular mediante una simple relación de recurrencia . [3]
Las escaleras de Möbius desempeñan un papel importante en la teoría de los grafos menores . El primer resultado de este tipo es un teorema de Klaus Wagner (1937) que afirma que los grafos sin menor K 5 se pueden formar utilizando operaciones de suma de clique para combinar grafos planares y la escalera de Möbius M 8 ; por esta razón, M 8 se denomina grafo de Wagner .
Gubser (1996) define un gráfico casi plano como un gráfico no plano para el cual cada menor no trivial es plano; muestra que los gráficos casi planos 3-conexos son escaleras de Möbius o miembros de un pequeño número de otras familias, y que otros gráficos casi planos pueden formarse a partir de estos mediante una secuencia de operaciones simples.
Maharry (2000) muestra que casi todos los gráficos que no tienen un cubo menor pueden derivarse mediante una secuencia de operaciones simples a partir de escaleras de Möbius.
Walba, Richards y Haltiwanger (1982) sintetizaron por primera vez estructuras moleculares en forma de escalera de Möbius, y desde entonces esta estructura ha sido de interés en química y estereografía química, [4] especialmente en vista de la forma de escalera de las moléculas de ADN. Con esta aplicación en mente, Flapan (1989) estudia las simetrías matemáticas de las incrustaciones de escaleras de Möbius en R 3 . En particular, como muestra, cada incrustación tridimensional de una escalera de Möbius con un número impar de peldaños es topológicamente quiral : no se puede convertir en su imagen especular mediante una deformación continua del espacio sin pasar un borde por otro. Por otro lado, todas las escaleras de Möbius con un número par de peldaños tienen incrustaciones en R 3 que se pueden deformar en sus imágenes especulares.
Las escaleras de Möbius también se han utilizado como forma de un anillo superconductor en experimentos para estudiar los efectos de la topología del conductor en las interacciones de los electrones. [5]
Las escaleras de Möbius también se han utilizado en informática , como parte de los enfoques de programación entera para problemas de empaquetamiento de conjuntos y ordenamiento lineal. Ciertas configuraciones dentro de estos problemas se pueden utilizar para definir facetas del politopo que describen una relajación de programación lineal del problema; estas facetas se denominan restricciones de escalera de Möbius. [6]