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

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

Свойства

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

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

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

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

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

Миноры графа

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

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

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

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

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

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

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

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

См. также

• Лента Мёбиуса
• Бутылка Клейна
• Граф-лестница

Примечания

Литература

• N. L. Biggs, R. M. Damerell, D. A. Sands. Recursive families of graphs // Journal of Combinatorial Theory . — 1972. — Т. 12 . — С. 123–131 . — doi : .
• G. Bolotashvili, M. Kovalev, E. Girlich. New facets of the linear ordering polytope // . — 1999. — Т. 12 , вып. 3 . — С. 326–336 . — doi : .
• Ralf Borndörfer, Robert Weismantel. Set packing relaxations of some integer programs // . — 2000. — Т. 88 , вып. 3 . — С. 425–450 . — doi : .
• Wen-Ji Deng, Ji-Huan Xu, Ping Liu. Period halving of persistent currents in mesoscopic Möbius ladders // . — 2002. — Т. 19 , вып. 7 . — С. 988–991 . — doi : . — arXiv : .
• Erica Flapan. // Mathematische Annalen . — 1989. — Т. 283 , вып. 2 . — С. 271–283 . — doi : .
• M. Grötschel, M. Jünger, G. Reinelt. On the acyclic subgraph polytope // . — 1985. — Т. 33 . — С. 28–42 . — doi : .
• M. Grötschel, M. Jünger, G. Reinelt. Facets of the linear ordering polytope // . — 1985. — Т. 33 . — С. 43–60 . — doi : .
• Bradley S. Gubser. A characterization of almost-planar graphs // Combinatorics, Probability and Computing. — 1996. — Т. 5 , вып. 3 . — С. 227–245 . — doi : .
• Richard K. Guy, Frank Harary. On the Möbius ladders // . — 1967. — Т. 10 . — С. 493–496 . — doi : .
• Dmitry Jakobson, Igor Rivin. On some extremal problems in graph theory. — 1999. — arXiv : .
• 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 : .
• John P. McSorley. Counting structures in the Möbius ladder // Discrete Mathematics . — 1998. — Т. 184 , вып. 1–3 . — С. 137–164 . — doi : .
• Anna De Mier, Marc Noy. On graphs determined by their Tutte polynomials // Graphs and Combinatorics. — 2004. — Т. 20 , вып. 1 . — С. 105–119 . — doi : .
• 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 : .
• 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 : .
• 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. // Mathematische Annalen. — 1937. — Т. 114 . — С. 570–590 . — doi : .
• 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 : .

Ссылки

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