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

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

Два представления лестницы Мёбиуса

\text{[math]}

M_{16}

M_{16}

.

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

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

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

СвойстваПравить

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

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

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

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

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

Миноры графаПравить

Граф Вагнера

\text{[math]}

M_{8}

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

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

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

Химия и физикаПравить

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

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

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

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

См. такжеПравить

ПримечанияПравить

↑ Максорли, 1998.
↑ Гай, Харари, 1967.
↑ Ли, 2005.
↑ Де Мье, Нуа, 2004.
↑ Якобсон, Ривин, 1999.
↑ Valdes, 1991.
↑ Биггс, Дэймрелл, Сэндс, 1972.
↑ Вагнер, 1937.
↑ Почти-планарный граф — непланарный граф, у которого любой нетривиальный минор планарен
↑ Gubser, 1996.
↑ Махарри, 2000.
↑ Вальба, Ричардс, Хальтивангер, 1982.
↑ Саймон, 1992.
↑ Флапан, 1989.
↑ Мила, Стаффорд, Каппони, 1998.
↑ Дэн, Сюй, Лю, 2002.
↑ Болоташвили, Ковалёв, Гирлич, 1999.
↑ Борндёрфер, Вайсмантель, 2000.
↑ Грётшель, Юнгер, Райнельт, 1985.
↑ Ньюмэн, Вемпала, 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.

[_5c573063ac4ee6b2-1] Максорли, 1998.

[_32204ececcdfd6d3-2] Гай, Харари, 1967.

[_d3117b1f8ac194ff-3] Ли, 2005.

[_b43417e679bfa131-4] Де Мье, Нуа, 2004.

[_bbb1c287491f3435-5] Якобсон, Ривин, 1999.

[_b22008d16b9d2d60-6] Valdes, 1991.

[_8ca62d1987edb4b6-7] Биггс, Дэймрелл, Сэндс, 1972.

[_1ad1eeb636de74bf-8] Вагнер, 1937.

[9] Почти-планарный граф — непланарный граф, у которого любой нетривиальный минор планарен

[_4a6413319086c5f2-10] Gubser, 1996.

[_9a0cafca074c3a0d-11] Махарри, 2000.

[_8911b94ae94068f1-12] Вальба, Ричардс, Хальтивангер, 1982.

[_6b5b481d3d97c7af-13] Саймон, 1992.

[_cbd768f0589ccdf1-14] Флапан, 1989.

[_165dd00ab19c4eb5-15] Мила, Стаффорд, Каппони, 1998.

[_e0e273734d1db4a1-16] Дэн, Сюй, Лю, 2002.

[_a293d7969baf3b2c-17] Болоташвили, Ковалёв, Гирлич, 1999.

[_1ef0480536ebb92c-18] Борндёрфер, Вайсмантель, 2000.

[_3a327332bab494db-19] Грётшель, Юнгер, Райнельт, 1985.

[_c1317c1c9f5539f7-20] Ньюмэн, Вемпала, 2001.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]