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

  1. ↑ Mc Sorley, 1998 .
  2. ↑ Chico, Harari, 1967 .
  3. ↑ Lee, 2005 .
  4. ↑ De Mieu, Nua, 2004 .
  5. ↑ Jacobson, Rivin, 1999 .
  6. ↑ Valdés, 1991 .
  7. ↑ Biggs, Daymrell, Sands, 1972 .
  8. ↑ Wagner, 1937 .
  9. ↑ Un gráfico casi plano  es un gráfico no plano para el cual cualquier menor no trivial es plano
  10. ↑ Gubser, 1996 .
  11. ↑ Maharri, 2000 .
  12. ↑ Walba, Richards, Haltiwanger 1982 .
  13. ↑ Simón, 1992 .
  14. ↑ Flapan, 1989 .
  15. ↑ Mila, Stafford, Capponi, 1998 .
  16. ↑ Deng, Xu, Liu, 2002 .
  17. ↑ Bolotashvili, Kovalev, Girlich, 1999 .
  18. ↑ Borndörfer, Weissmantel, 2000 .
  19. ↑ Grötschel, Jünger, Reinelt, 1985 .
  20. ↑ Newman, Vempala, 2001 .

Literatura

Enlaces