Лестница Мёбиуса

Два представления лестницы Мёбиуса ${\displaystyle M_{16}}$.

Анимация преобразования одного вида в другой

Представление лестницы Мёбиуса M₁₆ в виде ленты Мёбиуса.

Ле́стница Мёбиуса ${\displaystyle M_{n}}$ — кубический циркулянтный граф с чётным числом вершин ${\displaystyle n}$, образованный из цикла с ${\displaystyle n}$ вершинами путём добавления рёбер (называемых «перекладинами»), соединяющих противоположные пары вершин цикла. Назван так ввиду того, что ${\displaystyle M_{n}}$ состоит из ${\displaystyle n/2}$ циклов длины 4^[1], соединённых вместе общими рёбрами и образующих топологически ленту Мёбиуса. Полный двудольный граф ${\displaystyle K_{3,3}}$ (граф «домики и колодцы») является лестницей Мёбиуса ${\displaystyle M_{6}}$ (в отличие от остальных ${\displaystyle M_{6}}$ имеет дополнительные циклы длины 4).

Впервые изучены Гаем и Харари^[2].

Свойства

Любая лестница Мёбиуса является непланарным верхушечнным графом. Число скрещиваний лестницы Мёбиуса равно единице, и граф может быть вложен без самопересечений в тор или проективную плоскость (то есть является тороидальным графом). Ли^[3] изучил вложение этих графов в поверхности более высоких родов.

Лестницы Мёбиуса являются вершинно-транзитивными, но (за исключением ${\displaystyle M_{6}}$) не рёберно-транзитивными — каждое ребро цикла, из которого лестница образована, принадлежит единственному 4-рёберному циклу, в то время как каждая перекладина принадлежит двум таким циклам.

Если ${\displaystyle n\equiv 2{\pmod {4}}}$, то ${\displaystyle M_{n}}$ является двудольным. При ${\displaystyle n\equiv 2{\pmod {4}}}$ по теореме Брукса хроматическое число ${\displaystyle M_{n}}$ равно 3. Известно^[4], что лестница Мёбиуса однозначно определяется её многочленом Татта.

Лестница Мёбиуса ${\displaystyle M_{8}}$ имеет 392 остовных дерева. Этот граф и ${\displaystyle M_{6}}$ имеют наибольшее число остовных деревьев среди кубических графов с тем же числом вершин^[5][6]. Однако среди кубических графов с 10 вершинами наибольшее число остовных деревьев у графа Петерсена, который не является лестницей Мёбиуса.

Многочлены Татта лестниц Мёбиуса можно получить по простой рекуррентной формуле^[7].

Миноры графа

Граф Вагнера ${\displaystyle M_{8}}$

Лестницы Мёбиуса играют важную роль в теории миноров графа. Самым ранним результатом такого типа является теорема Вагнера^[8] о том, что граф, не содержащий ${\displaystyle K_{5}}$-миноров, может быть образован с использованием сумм по клике для комбинирования планарных графов и лестницы Мёбиуса ${\displaystyle M_{8}}$ (в этой связи ${\displaystyle M_{n}}$ называют графом Вагнера.

Все 3-связные почти-планарные графы^[9] являются лестницами Мёбиуса или принадлежат небольшому числу других семейств, притом остальные почти-планарные графы можно получить из этих графов с помощью ряда простых операций^[10].

Почти все^{[уточнить]} графы, не содержащие куб в качестве минора, могут быть получены из лестниц Мёбиуса в результате последовательного применения простых операций^[11].

Химия и физика

В 1982 году синтезирована молекулярная структура, имеющую форму лестницы Мёбиуса^[12], и с тех пор такие графы представляют интерес для химиков и химической стереографии^[13], особенно в свете похожих на лестницу Мёбиуса молекул ДНК. Имея это в виду, особо изучены математические симметрии вложений лестниц Мёбиуса в ${\displaystyle \mathbb {R} ^{3}}$^[14].

Лестницы Мёбиуса используются как модель сверхпроводимого кольца в экспериментах по изучению эффектов топологии проводимости при взаимодействии электронов^[15][16].

Комбинаторная оптимизация

Лестницы Мёбиуса используются также в информатике как часть подхода целочисленного программирования к задачам упаковки множеств и линейного упорядочивания. Некоторые конфигурации в этих задачах могут быть использованы для определения граней политопов, описывающих ослабление условий^[англ.] линейного программирования. Эти грани называются ограничениями лестниц Мёбиуса^{[17][18][19][20]}.

См. также

• Лента Мёбиуса
• Странная петля^[англ.]
• Бутылка Клейна
• Граф-лестница

Примечания

1. Максорли, 1998.
2. Гай, Харари, 1967.
3. Ли, 2005.
4. Де Мье, Нуа, 2004.
5. Якобсон, Ривин, 1999.
6. Valdes, 1991.
7. Биггс, Дэймрелл, Сэндс, 1972.
8. Вагнер, 1937.
9. Почти-планарный граф — непланарный граф, у которого любой нетривиальный минор планарен
10. Gubser, 1996.
11. Махарри, 2000.
12. Вальба, Ричардс, Хальтивангер, 1982.
13. Саймон, 1992.
14. Флапан, 1989.
15. Мила, Стаффорд, Каппони, 1998.
16. Дэн, Сюй, Лю, 2002.
17. Болоташвили, Ковалёв, Гирлич, 1999.
18. Борндёрфер, Вайсмантель, 2000.
19. Грётшель, Юнгер, Райнельт, 1985.
20. Ньюмэн, Вемпала, 2001.

Литература

• N. L. Biggs, R. M. Damerell, D. A. Sands. Recursive families of graphs // Journal of Combinatorial Theory. — 1972. — Т. 12. — С. 123–131. — doi:10.1016/0095-8956(72)90016-0.
• G. Bolotashvili, M. Kovalev, E. Girlich. New facets of the linear ordering polytope // SIAM Journal on Discrete Mathematics. — 1999. — Т. 12, вып. 3. — С. 326–336. — doi:10.1137/S0895480196300145.
• Ralf Borndörfer, Robert Weismantel. Set packing relaxations of some integer programs // Mathematical Programming. — 2000. — Т. 88, вып. 3. — С. 425–450. — doi:10.1007/PL00011381.
• Wen-Ji Deng, Ji-Huan Xu, Ping Liu. Period halving of persistent currents in mesoscopic Möbius ladders // Chinese Physics Letters. — 2002. — Т. 19, вып. 7. — С. 988–991. — doi:10.1088/0256-307X/19/7/333. — arXiv:cond-mat/0209421.
• Erica Flapan. Symmetries of Möbius ladders // Mathematische Annalen. — 1989. — Т. 283, вып. 2. — С. 271–283. — doi:10.1007/BF01446435.
• M. Grötschel, M. Jünger, G. Reinelt. On the acyclic subgraph polytope // Mathematical Programming. — 1985. — Т. 33. — С. 28–42. — doi:10.1007/BF01582009.
• M. Grötschel, M. Jünger, G. Reinelt. Facets of the linear ordering polytope // Mathematical Programming. — 1985. — Т. 33. — С. 43–60. — doi:10.1007/BF01582010.
• Bradley S. Gubser. A characterization of almost-planar graphs // Combinatorics, Probability and Computing. — 1996. — Т. 5, вып. 3. — С. 227–245. — doi:10.1017/S0963548300002005.
• Richard K. Guy, Frank Harary. On the Möbius ladders // Canadian Mathematical Bulletin. — 1967. — Т. 10. — С. 493–496. — doi:10.4153/CMB-1967-046-4.
• Dmitry Jakobson, Igor Rivin. On some extremal problems in graph theory. — 1999. — arXiv:math.CO/9907050.
• De-ming Li. Genus distributions of Möbius ladders // Northeastern Mathematics Journal. — 2005. — Т. 21, вып. 1. — С. 70–80.
• John Maharry. A characterization of graphs with no cube minor // Journal of Combinatorial Theory. — 2000. — Т. 80, вып. 2. — С. 179–201. — doi:10.1006/jctb.2000.1968.
• John P. McSorley. Counting structures in the Möbius ladder // Discrete Mathematics. — 1998. — Т. 184, вып. 1–3. — С. 137–164. — doi:10.1016/S0012-365X(97)00086-1.
• Anna De Mier, Marc Noy. On graphs determined by their Tutte polynomials // Graphs and Combinatorics. — 2004. — Т. 20, вып. 1. — С. 105–119. — doi:10.1007/s00373-003-0534-z.
• Frédéric Mila, C. A. Stafford, Sylvain Capponi. Persistent currents in a Möbius ladder: A test of interchain coherence of interacting electrons // Physical Review B. — 1998. — Т. 57, вып. 3. — С. 1457–1460. — doi:10.1103/PhysRevB.57.1457.
• Alantha Newman, Santosh Vempala. Integer Programming and Combinatorial Optimization: 8th International IPCO Conference, Utrecht, The Netherlands, June 13–15, 2001, Proceedings. — Berlin: Springer-Verlag, 2001. — Т. 2081. — С. 333–347. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-45535-3_26.
• Jonathan Simon. New scientific applications of geometry and topology (Baltimore, MD, 1992). — Providence, RI: American Mathematical Society, 1992. — Т. 45. — С. 97–130. — (Proceedings of Symposia in Applied Mathematics).
• L. Valdes. Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991). — 1991. — Т. 85. — С. 143–160. — (Congressus Numerantium).
• K. Wagner. Über eine Eigenschaft der ebenen Komplexe // Mathematische Annalen. — 1937. — Т. 114. — С. 570–590. — doi:10.1007/BF01594196.
• D. Walba, R. Richards, R. C. Haltiwanger. Total synthesis of the first molecular Möbius strip // Journal of the American Chemical Society. — 1982. — Т. 104, вып. 11. — С. 3219–3221. — doi:10.1021/ja00375a051.

Ссылки

• Weisstein, Eric W. Möbius Ladder (англ.) на сайте Wolfram MathWorld.