Escalera de Möbius
La escalera de Möbius es un grafo circulante cúbico con un número par de vértices , formado a partir de un ciclo con vértices añadiendo aristas (llamadas "peldaños") que conectan pares opuestos de vértices de ciclo. Llamada así porque consiste en ciclos de longitud 4 [1] conectados entre sí por aristas comunes y formando topológicamente una cinta de Möbius . El grafo bipartito completo (gráfico “ casas y pozos ”) es una escalera de Möbius (a diferencia de los demás, tiene ciclos adicionales de longitud 4).
Primero estudiado por Guy y Harari [2] .
Propiedades
Cualquier escalera de Möbius es un grafo de vértice no plano . El número de cruces de la escalera de Möbius es uno, y el grafo se puede incrustar sin autointersecciones en un toro o plano proyectivo (es decir, es un grafo toroidal ). Lee [3] estudió la incrustación de estos gráficos en superficies de género superior.
Las escaleras de Möbius son de vértice transitivo , pero (con la excepción de ) no de borde transitivo : cada borde del ciclo a partir del cual se forma la escalera pertenece a un solo ciclo de 4 bordes, mientras que cada peldaño pertenece a dos de esos ciclos.
Si , entonces es bipartito . Cuando , según el teorema de Brooks , el número cromático es 3. Se sabe [4] que la escalera de Möbius está determinada únicamente por su polinomio de Tatta .
La escalera de Möbius tiene 392 árboles de expansión . Este gráfico también tiene el mayor número de árboles de expansión entre los gráficos cúbicos con el mismo número de vértices [5] [6] . Sin embargo, entre los gráficos cúbicos con 10 vértices, el gráfico de Petersen tiene el mayor número de árboles de expansión , que no es una escalera de Möbius.
Los polinomios de Tutt de las escaleras de Möbius se pueden obtener mediante una fórmula recursiva simple [7] .
Contar menores
Las escaleras de Möbius juegan un papel importante en la teoría de grafos menores . El primer resultado de este tipo es el teorema de Wagner [8] de que se puede formar un grafo que no contenga -menores usando sumas clique para combinar gráficos planos y la escalera de Möbius (en este sentido llamado grafo de Wagner) .
Todos los gráficos casi planos conectados en 3 [9] son escaleras de Möbius o pertenecen a un pequeño número de otras familias, y el resto de los gráficos casi planos se pueden obtener a partir de estos gráficos mediante una serie de operaciones simples [10] .
Casi todos[ aclarar ] Los gráficos que no contienen un cubo como menor se pueden obtener de las escaleras de Möbius como resultado de la aplicación secuencial de operaciones simples [11] .
Química y física
En 1982, se sintetizó una estructura molecular en forma de escalera de Möbius [12] , y desde entonces dichos gráficos han sido de interés para los químicos y la estereografía química [13] , especialmente a la luz de las moléculas de ADN similares a la escalera de Möbius. Con esto en mente, las simetrías matemáticas de las incrustaciones de las escaleras de Möbius se han estudiado especialmente en [14] .
Las escaleras de Möbius se utilizan como modelo de un anillo superconductor en experimentos para estudiar los efectos de la topología de conducción en la interacción de electrones [15] [16] .
Optimización combinatoria
Las escaleras de Möbius también se utilizan en informática como parte de un enfoque de programación de enteros para establecer problemas de ordenamiento lineal y empaquetado. Algunas configuraciones en estos problemas se pueden usar para definir caras de politopos que describen la relajación de las condiciones de la programación lineal . Estas caras se denominan restricciones de las escaleras de Möbius [17] [18] [19] [20] .
Véase también
Notas
- ↑ Mc Sorley, 1998 .
- ↑ Chico, Harari, 1967 .
- ↑ Lee, 2005 .
- ↑ De Mieu, Nua, 2004 .
- ↑ Jacobson, Rivin, 1999 .
- ↑ Valdés, 1991 .
- ↑ Biggs, Daymrell, Sands, 1972 .
- ↑ Wagner, 1937 .
- ↑ Un gráfico casi plano es un gráfico no plano para el cual cualquier menor no trivial es plano
- ↑ Gubser, 1996 .
- ↑ Maharri, 2000 .
- ↑ Walba, Richards, Haltiwanger 1982 .
- ↑ Simón, 1992 .
- ↑ Flapan, 1989 .
- ↑ Mila, Stafford, Capponi, 1998 .
- ↑ Deng, Xu, Liu, 2002 .
- ↑ Bolotashvili, Kovalev, Girlich, 1999 .
- ↑ Borndörfer, Weissmantel, 2000 .
- ↑ Grötschel, Jünger, Reinelt, 1985 .
- ↑ Newman, Vempala, 2001 .
Literatura
- NL Biggs, RM Damerell, DA Sands. Familias recursivas de grafos // Journal of Combinatorial Theory . - 1972. - T. 12 . — S. 123–131 . - doi : 10.1016/0095-8956(72)90016-0 .
- G. Bolotashvili, M. Kovalev, E. Girlich. Nuevas facetas del politopo de ordenación lineal // SIAM Journal on Discrete Mathematics . - 1999. - T. 12 , núm. 3 . — S. 326–336 . -doi : 10.1137/ S0895480196300145 .
- Ralf Borndorfer, Robert Weismantel. Establecer relajaciones de empaquetamiento de algunos programas enteros // Programación matemática . - 2000. - T. 88 , núm. 3 . — S. 425–450 . -doi : 10.1007/ PL00011381 .
- Wen-Ji Deng, Ji-Huan Xu, Ping Liu. Período de reducción a la mitad de corrientes persistentes en escaleras mesoscópicas de Möbius // Cartas de física china . - 2002. - T. 19 , nº. 7 . — S. 988–991 . -doi : 10.1088 / 0256-307X/19/7/333 . -arXiv : cond - mat/0209421 .
- Érica Flapan. Simetrías de las escaleras de Möbius // Mathematische Annalen . - 1989. - T. 283 , núm. 2 . — S. 271–283 . -doi : 10.1007/ BF01446435 .
- M. Grötschel, M. Junger, G. Reinelt. Sobre el politopo subgráfico acíclico // Programación Matemática . - 1985. - T. 33 . — P. 28–42 . -doi : 10.1007/ BF01582009 .
- M. Grötschel, M. Junger, G. Reinelt. Facetas del politopo de ordenación lineal // Programación Matemática . - 1985. - T. 33 . — P. 43–60 . -doi : 10.1007/ BF01582010 .
- Bradley S. Gubser. Una caracterización de grafos casi planos // Combinatoria, Probabilidad y Computación. - 1996. - V. 5 , núm. 3 . — S. 227–245 . - doi : 10.1017/S0963548300002005 .
- Richard K. Guy, Frank Harary. En las escaleras de Möbius // Canadian Mathematical Bulletin . - 1967. - T. 10 . — S. 493–496 . -doi : 10.4153 / CMB-1967-046-4 .
- Dmitri Jakobson, Igor Rivin. Sobre algunos problemas extremos en teoría de grafos. - 1999. - arXiv : math.CO/9907050 .
- Deming Li. Distribuciones de género de las escaleras de Möbius // Northeastern Mathematics Journal. - 2005. - T. 21 , núm. 1 . — S. 70–80 .
- Juan Maharry. Una caracterización de grafos sin cubo menor // Journal of Combinatorial Theory . - 2000. - T. 80 , núm. 2 . — S. 179–201 . -doi : 10.1006/ jctb.2000.1968 .
- John P. Mc Sorley. Estructuras de conteo en la escalera de Möbius // Matemáticas discretas . - 1998. - T. 184 , núm. 1–3 . — S. 137–164 . - doi : 10.1016/S0012-365X(97)00086-1 .
- Anna De Mier, Marc Noy. Sobre grafos determinados por sus polinomios de Tutte // Grafos y Combinatoria. - 2004. - T. 20 , núm. 1 . — S. 105–119 . -doi : 10.1007 / s00373-003-0534-z .
- Frederic Mila, CA Stafford, Sylvain Capponi. Corrientes persistentes en una escalera de Möbius: una prueba de coherencia entre cadenas de electrones que interactúan // Revisión física B . - 1998. - T. 57 , núm. 3 . - S. 1457-1460 . -doi : 10.1103 / PhysRevB.57.1457 .
- Alantha Newman, Santosh Vempala. Programación de enteros y optimización combinatoria: 8.ª Conferencia internacional de IPCO, Utrecht, Países Bajos, 13 al 15 de junio de 2001, Actas. - Berlín: Springer-Verlag, 2001. - T. 2081. - S. 333-347. — (Apuntes de clase en informática). -doi : 10.1007/ 3-540-45535-3_26 .
- Jonathan Simón. Nuevas aplicaciones científicas de geometría y topología (Baltimore, MD, 1992). - Providence, RI: American Mathematical Society , 1992. - V. 45. - P. 97-130. - (Actas de simposios de matemáticas aplicadas).
- L. Valdés. Actas de la Vigésima segunda Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Baton Rouge, LA, 1991). - 1991. - T. 85. - S. 143-160. — (Congressus Numerantium).
- K. Wagner. Über eine Eigenschaft der ebenen Komplexe // Mathematische Annalen. - 1937. - T. 114 . — S. 570–590 . -doi : 10.1007/ BF01594196 .
- D. Walba, R. Richards, R. C. Haltiwanger. Síntesis total de la primera tira de Möbius molecular // Journal of the American Chemical Society. - 1982. - T. 104 , núm. 11 _ — S. 3219–3221 . -doi : 10.1021/ ja00375a051 .
Enlaces