Gráfico de ciclo con todos los nodos opuestos vinculados
En teoría de grafos , la escalera de Möbius M n , para números pares n , se forma a partir de un n ciclo agregando aristas (llamadas "peldaños") que conectan pares opuestos de vértices en el ciclo. Es un gráfico circulante cúbico , llamado así porque (con la excepción de M 6 (el gráfico de utilidad K 3,3 ), M n tiene exactamente n /2 cuatro ciclos [1] que se unen por sus aristas compartidas para Forman una franja topológica de Möbius . Las escaleras de Möbius fueron nombradas y estudiadas por primera vez por Guy y Harary (1967).
Propiedades
Para cada par n > 4 , la escalera de Möbius M n es un gráfico de vértices no plano , lo que significa que no se puede dibujar sin cruces en el plano, pero eliminar un vértice permite dibujar el gráfico restante sin cruces. Estos gráficos tienen el cruce número uno y se pueden incrustar sin cruces en un toroide o plano proyectivo . Por tanto, son ejemplos de gráficas toroidales . Li (2005) explora las incrustaciones de estos gráficos en superficies de géneros superiores.
Las escaleras de Möbius son transitivas por vértices (tienen simetrías que llevan cualquier vértice a cualquier otro), pero (con las excepciones de M 4 y M 6 ) no son transitivas por aristas . Los bordes del ciclo a partir del cual se forma la escalera se pueden distinguir de los peldaños de la escalera, porque cada borde del ciclo pertenece a un solo 4 ciclos, mientras que cada peldaño pertenece a dos de esos ciclos. Por lo tanto, no existe simetría al llevar un borde de ciclo a un borde 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 agregar cada peldaño crea un ciclo impar. En este caso, debido a que la gráfica es 3-regular pero no bipartita, según 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 únicamente por sus polinomios de Tutte .
La escalera de Möbius M 8 tiene 392 árboles de expansión ; it y M 6 tienen la mayor cantidad de árboles de expansión entre todos los gráficos cúbicos con el mismo número de vértices. [2] Sin embargo, el gráfico cúbico de 10 vértices con más árboles de expansión es el gráfico de Petersen , que no es una escalera de Möbius.
Las escaleras de Möbius juegan un papel importante en la teoría de grafos menores . El primer resultado de este tipo es un teorema de Klaus Wagner (1937) de que se pueden formar gráficos sin K 5 menor utilizando operaciones de suma camarilla para combinar gráficos planos y la escalera de Möbius M 8 ; por esta razón M 8 se llama gráfico de Wagner .
Gubser (1996) define un grafo casi plano como un grafo no plano para el cual todo menor no trivial es plano; muestra que los gráficos casi planos de 3 conectados son escaleras de Möbius o miembros de un pequeño número de otras familias, y que se pueden formar otros gráficos casi planos 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 de las escaleras de Möbius.
quimica y fisica
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 en 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 ella muestra, cada incrustación tridimensional de una escalera de Möbius con un número impar de peldaños es topológicamente quiral : no puede convertirse en su imagen especular mediante una deformación continua del espacio sin pasar un borde a través de otro. Por otro lado, las escaleras de Möbius con un número par de peldaños tienen todas incrustaciones en R 3 que pueden deformarse en 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]
Optimización combinatoria
Las escaleras de Möbius también se han utilizado en informática , como parte de enfoques de programación entera para problemas de empaquetado de conjuntos y ordenamiento lineal. Ciertas configuraciones dentro de estos problemas se pueden usar 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]
Bolotashvili, G.; Kovalev, M.; Girlich, E. (1999). "Nuevas facetas del politopo de ordenamiento lineal". Revista SIAM de Matemática Discreta . 12 (3): 326–336. CiteSeerX 10.1.1.41.8722 . doi :10.1137/S0895480196300145. SEÑOR 1710240.
Borndörfer, Ralf; Weismantel, Robert (2000). "Establecer relajaciones de empaquetado de algunos programas de números enteros". Programación Matemática . Serie A. 88 (3): 425–450. doi :10.1007/PL00011381. SEÑOR 1782150. S2CID 206862305.
Deng, Wen-Ji; Xu, Ji-Huan; Liu, Ping (2002). "Período de reducción a la mitad de las corrientes persistentes en escaleras mesoscópicas de Möbius". Letras de Física China . 19 (7): 988–991. arXiv : cond-mat/0209421 . Código Bib :2002ChPhL..19..988D. doi :10.1088/0256-307X/19/7/333. S2CID 119421223.
Grötschel, M .; Jünger, M.; Reinelt, G. (1985a). "Sobre el politopo del subgrafo acíclico". Programación Matemática . 33 : 28–42. doi :10.1007/BF01582009. SEÑOR 0809747. S2CID 206798683.
Grötschel, M.; Jünger, M.; Reinelt, G. (1985b). "Facetas del politopo de ordenamiento lineal". Programación Matemática . 33 : 43–60. doi :10.1007/BF01582010. SEÑOR 0809748. S2CID 21071064.
Jakobson, Dmitry; Rivin, Igor (1999). "Sobre algunos problemas extremos en teoría de grafos". arXiv : math.CO/9907050 .
Li, Deming (2005). "Distribuciones de géneros de escaleras de Möbius". Revista de Matemáticas del Noreste . 21 (1): 70–80. SEÑOR 2124859.
Maharry, John (2000). "Una caracterización de gráficos sin cubo menor". Revista de teoría combinatoria . Serie B. 80 (2): 179–201. doi : 10.1006/jctb.2000.1968 . SEÑOR 1794690.
McSorley, John P. (1998). "Contando estructuras en la escalera de Möbius". Matemáticas discretas . 184 (1–3): 137–164. doi : 10.1016/S0012-365X(97)00086-1 . SEÑOR 1609294.
De Mier, Anna; Noy, Marc (2004). "Sobre gráficas determinadas por sus polinomios de Tutte". Gráficas y Combinatoria . 20 (1): 105-119. doi :10.1007/s00373-003-0534-z. SEÑOR 2048553. S2CID 46312268.
Mila, Federico; Stafford, California; Capponi, Sylvain (1998). "Corrientes persistentes en una escalera de Möbius: una prueba de coherencia entre cadenas de electrones que interactúan" (PDF) . Revisión física B. 57 (3): 1457-1460. arXiv : cond-mat/9705119 . Código bibliográfico : 1998PhRvB..57.1457M. doi : 10.1103/PhysRevB.57.1457. S2CID 35931632.
Newman, Alanta; Vempala, Santosh (2001). "Las vallas son inútiles: sobre flexibilizaciones para el problema de ordenamiento lineal". Programación entera y optimización combinatoria: octava conferencia internacional IPCO, Utrecht, Países Bajos, 13 al 15 de junio de 2001, Actas . Apuntes de conferencias sobre informática. vol. 2081. Berlín: Springer-Verlag. págs. 333–347. doi :10.1007/3-540-45535-3_26. SEÑOR 2041937. Archivado desde el original el 2 de enero de 2004 . Consultado el 8 de octubre de 2006 .
Simón, Jonathan (1992). "Nudos y química". Nuevas aplicaciones científicas de la geometría y la topología (Baltimore, MD, 1992) . Actas de simposios en matemáticas aplicadas. vol. 45. Providence, RI: Sociedad Matemática Estadounidense . págs. 97-130. SEÑOR 1196717.
Valdés, L. (1991). "Propiedades extremas de árboles generadores en gráficos cúbicos". Actas de la Vigésima Segunda Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Baton Rouge, LA, 1991) . Congreso Numerantium. vol. 85, págs. 143-160. SEÑOR 1152127.
Wagner, K. (1937). "Über eine Eigenschaft der ebenen Komplexe". Annalen Matemáticas . 114 : 570–590. doi :10.1007/BF01594196. SEÑOR 1513158. S2CID 123534907.
Walba, D.; Richards, R.; Haltiwanger, RC (1982). "Síntesis total de la primera tira de Möbius molecular". Revista de la Sociedad Química Estadounidense . 104 (11): 3219–3221. doi :10.1021/ja00375a051.
