En la teoría de grafos , la escalera de Möbius M n es un cúbico gráfico circulant con un número par n de vértices, formado a partir de un n - ciclo mediante la adición de bordes (llamado "peldaños") que conecta los pares opuestos de vértices en el ciclo. Se llama así porque (con la excepción de M 6 = K 3,3 ) M n tiene exactamente n / 2 4 ciclos [1] que se unen por sus bordes compartidos para formar una tira topológica de Möbius . Las escaleras de Moebius fueron nombradas y estudiadas por primera vez por Guyy Harary ( 1967 ).
Propiedades
Cada escalera de Möbius es un gráfico de vértice 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. Las escaleras de Möbius tienen el cruce número uno y se pueden empotrar sin cruces en un plano toroidal o proyectivo . Por tanto, son ejemplos de gráficos toroidales . Li (2005) explora las incrustaciones de estos gráficos en superficies de géneros superiores.
Las escaleras de Möbius son transitivas de vértice , tienen simetrías que llevan cualquier vértice a cualquier otro vértice, pero (de nuevo con la excepción de M 6 ) no son transitivas de borde . 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 ciclo de 4, mientras que cada peldaño pertenece a dos de tales ciclos. Por lo tanto, no hay simetría que lleve 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 el gráfico es 3-regular pero no bipartito, según el teorema de Brooks tiene un 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 Möbius M 8 tiene 392 árboles extensibles ; it y M 6 tienen la mayor cantidad de árboles de expansión entre todas las gráficas cúbicas 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.
Los polinomios de Tutte de las escaleras de Möbius pueden calcularse mediante una relación de recurrencia simple . [3]
Graficar menores
Las escaleras de Möbius juegan un papel importante en la teoría de grafos menores . El resultado más temprano de este tipo es un teorema de Klaus Wagner ( 1937 ) según el cual los gráficos sin K 5 menor se pueden formar usando operaciones de suma de clique para combinar gráficos planos y la escalera de Möbius M 8 ; por esta razón, M 8 se denomina 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 las gráficas casi planas de 3 conexiones son escaleras de Möbius o miembros de un pequeño número de otras familias, y que otras gráficas casi planas pueden formarse a partir de ellas mediante una secuencia de operaciones simples.
Maharry (2000) muestra que casi todas las gráficas que no tienen un cubo menor pueden derivarse mediante una secuencia de operaciones simples de las escaleras de Möbius.
Química y física
Walba, Richards & 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 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 las 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 de un borde a otro. Por otro lado, las escaleras de Möbius con un número par de peldaños tienen incrustaciones en R 3 que pueden deformarse en sus imágenes especulares.
Las escaleras de Möbius también se han utilizado como forma de anillo superconductor en experimentos para estudiar los efectos de la topología de los conductores 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 de enteros para problemas de empaquetado de conjuntos y ordenamiento lineal. Ciertas configuraciones dentro de estos problemas pueden usarse 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]
Ver también
- Gráfico de escalera
- Gráfico de prisma
Notas
- ^ McSorley (1998) .
- ^ Jakobson y Rivin (1999) ; Valdés (1991) .
- ^ Biggs, Damerell y Sands (1972) .
- ^ Simon (1992) .
- ^ Mila, Stafford y Capponi (1998) ; Deng, Xu y Liu (2002) .
- ^ Bolotashvili, Kovalev y Girlich (1999) ; Borndörfer y Weismantel (2000) ; Grötschel, Jünger y Reinelt ( 1985a , 1985b ); Newman y Vempala (2001)
Referencias
- Biggs, NL ; Damerell, RM; Sands, DA (1972). "Familias recursivas de gráficos" . Revista de teoría combinatoria . Serie B 12 (2): 123-131. doi : 10.1016 / 0095-8956 (72) 90016-0 . Señor 0294172 .
- 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 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 corrientes persistentes en escaleras mesoscópicas de Möbius". Letras de física chinas . 19 (7): 988–991. arXiv : cond-mat / 0209421 . Código bibliográfico : 2002ChPhL..19..988D . doi : 10.1088 / 0256-307X / 19/7/333 . S2CID 119421223 .
- Flapan, Erica (1989). "Simetrías de escaleras de Möbius". Mathematische Annalen . 283 (2): 271–283. doi : 10.1007 / BF01446435 . Señor 0980598 . S2CID 119705062 .
- Grötschel, M .; Jünger, M .; Reinelt, G. (1985a). "Sobre el politopo subgráfico 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 .
- Gubser, Bradley S. (1996). "Una caracterización de grafos casi planos". Combinatoria, Probabilidad y Computación . 5 (3): 227–245. doi : 10.1017 / S0963548300002005 . Señor 1411084 .
- Guy, Richard K .; Harary, Frank (1967). "En las escaleras de Möbius". Boletín matemático canadiense . 10 (4): 493–496. doi : 10.4153 / CMB-1967-046-4 . Señor 0224499 .
- Jakobson, Dmitry; Rivin, Igor (1999). "Sobre algunos problemas extremos en teoría de grafos" . arXiv : math.CO/9907050 . Cite journal requiere
|journal=
( ayuda ) - Li, De-ming (2005). "Distribuciones de género 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áficos determinados por sus polinomios de Tutte". Gráficos y Combinatoria . 20 (1): 105-119. doi : 10.1007 / s00373-003-0534-z . Señor 2048553 . S2CID 46312268 .
- Mila, Frédéric; Stafford, CA; Capponi, Sylvain (1998). "Corrientes persistentes en una escalera de Möbius: una prueba de coherencia entre cadenas de electrones que interactúan" (PDF) . Physical Review 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, Alantha; Vempala, Santosh (2001). "Las vallas son inútiles: en relajaciones para el problema de ordenamiento lineal" . Programación de enteros y optimización combinatoria: 8ª Conferencia Internacional de IPCO, Utrecht, Países Bajos, 13-15 de junio de 2001, Actas . Apuntes de conferencias en Ciencias de la Computación. 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 .
- Simon, Jonathan (1992). "Nudos y química". Nuevas aplicaciones científicas de geometría y topología (Baltimore, MD, 1992) . Actas de simposios en matemáticas aplicadas. 45 . Providence, RI: Sociedad Matemática Estadounidense . págs. 97–130. Señor 1196717 .
- Valdés, L. (1991). "Propiedades extremas de los árboles de expansión en gráficos cúbicos". Actas de la Vigésima Segunda Conferencia del Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Baton Rouge, LA, 1991) . Congressus Numerantium. 85 . págs. 143-160. Señor 1152127 .
- Wagner, K. (1937). "Über eine Eigenschaft der ebenen Komplexe". Mathematische Annalen . 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 molecular de Möbius". Revista de la Sociedad Química Estadounidense . 104 (11): 3219–3221. doi : 10.1021 / ja00375a051 .
enlaces externos
- Weisstein, Eric W. "Escalera de Möbius" . MathWorld .