Драбина Мебіуса

Драби́на Ме́біуса  — кубічний циркулянтний граф з парним числом вершин , утворений з циклу з вершинами шляхом додавання ребер (званих «щаблями»), що з'єднують протилежні пари вершин циклу. Названий так через те, що складається з циклів довжини 4[1], з'єднаних разом спільними ребрами, які утворюють топологічно стрічку Мебіуса. Повний дводольний граф (граф «Вода, газ та електрика») є драбиною Мебіуса (на відміну від інших має додаткові цикли довжини 4).

Два подання драбини Мебіуса .
Анімація перетворення одного виду в інший
Подання драбини Мебіуса M16 у вигляді стрічки Мебіуса.

Якщо , то є двочастковим. При за теоремою Брукса хроматичне число дорівнює 3. Відомо[2], що драбина Мебіуса однозначно визначається її многочленом Татта.

Властивості

Будь-які сходи Мебіуса є непланарним вершинним графом. Кількість схрещувань драбини Мебіуса дорівнює одиниці, і граф можна вкласти без самоперетинів у тор або проєктивну площину (тобто є тороїдальним графом). Лі[3] вивчив вкладення цих графів у поверхні більш високих родів.

Драбини Мебіуса є вершинно-транзитивними, але (за винятком ) не реберно-транзитивними — кожне ребро циклу, з якого драбину утворено, належить єдиному 4-реберному циклу, тоді як кожна перекладина належить двом таким циклам.

Драбина Мебіуса має 392 кістякових дерева. Цей граф і мають найбільше число кістякових дерев серед кубічних графів з тим самим числом вершин[4][5]. Однак серед кубічних графів з 10 вершинами найбільше число кістякових дерев має граф Петерсена, який не є драбиною Мебіуса.

Многочлени Татта драбин Мебіуса можна отримати за простою рекурентною формулою[6].

Мінори графу
Граф Вагнера

Драбини Мебіуса відіграють важливу роль у теорії мінорів графу. Найранішим результатом такого типу є теорема Вагнера[7] про те, що граф, який не містить -мінорів, можна утворити з використанням сум за клікою для комбінування планарних графів і драбини Мебіуса (через це називають графом Вагнера.

Всі 3-зв'язні майже-планарні графи[8] є драбинами Мебіуса або належать невеликого числа інших сімейств, причому решту майже-планарних графів можна отримати з цих графів за допомогою низки простих операцій[9].

Майже всі[уточнити] графи, які не містять куба як мінора, можна отримати з драбини Мебіуса послідовним застосуванням простих операцій[10].

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

В 1982 році синтезовано молекулярну структуру, що має форму сходів Мебіуса[11], і відтоді такі графи становлять інтерес для хіміків і хімічної стереографії[12], зокрема через схожість на драбину Мебіуса молекул ДНК. Зважаючи на це, особливо вивчено математичні симетрії вкладень драбин Мебіуса в [13].

Драбини Мебіуса використовують як модель надпровідного кільця в експериментах з вивчення ефектів топології провідності при взаємодії електронів[14][15].

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

Драбини Мебіуса використовують також в інформатиці в межах підходу цілочисельного програмування до задач пакування множин і лінійного впорядкування. Деякі конфігурації в цих задачах можна використати для визначення граней політопів, що описують ослаблення умов лінійного програмування. Ці грані називають обмеженнями драбин Мебіуса[16][17][18][19].

Див. також

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

Література
  • N. L. Biggs, R. M. Damerell, D. A. Sands. Recursive families of graphs // Journal of Combinatorial Theory. — 1972. — Т. 12 (7 лютого). — С. 123–131. — (Series B). — 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 (7 лютого). — С. 326–336. — DOI:10.1137/S0895480196300145.
  • Ralf Borndörfer, Robert Weismantel. Set packing relaxations of some integer programs // Mathematical Programming. — 2000. — Т. 88, вип. 3 (7 лютого). — С. 425–450. — (Series A). — 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 (7 лютого). — С. 988–991. — arXiv:cond-mat/0209421. — DOI:10.1088/0256-307X/19/7/333.
  • Erica Flapan. Symmetries of Möbius ladders // Mathematische Annalen. — 1989. — Т. 283, вип. 2 (7 лютого). — С. 271–283. — DOI:10.1007/BF01446435.
  • M. Grötschel, M. Jünger, G. Reinelt. On the acyclic subgraph polytope // Mathematical Programming. — 1985. — Т. 33 (7 лютого). — С. 28–42. — DOI:10.1007/BF01582009.
  • M. Grötschel, M. Jünger, G. Reinelt. Facets of the linear ordering polytope // Mathematical Programming. — 1985. — Т. 33 (7 лютого). — С. 43–60. — DOI:10.1007/BF01582010.
  • Bradley S. Gubser. A characterization of almost-planar graphs // Combinatorics, Probability and Computing. — 1996. — Т. 5, вип. 3 (7 лютого). — С. 227–245. — DOI:10.1017/S0963548300002005.
  • Richard K. Guy, Frank Harary. On the Möbius ladders // Canadian Mathematical Bulletin. — 1967. — Т. 10 (7 лютого). — С. 493–496. — DOI:10.4153/CMB-1967-046-4.
  • Dmitry Jakobson, Igor Rivin. On some extremal problems in graph theory. — 1999. — 7 лютого. — arXiv:math.CO/9907050.
  • De-ming Li. Genus distributions of Möbius ladders // Northeastern Mathematics Journal. — 2005. — Т. 21, вип. 1 (7 лютого). — С. 70–80.
  • John Maharry. A characterization of graphs with no cube minor // Journal of Combinatorial Theory. — 2000. — Т. 80, вип. 2 (7 лютого). — С. 179–201. — (Series B). — DOI:10.1006/jctb.2000.1968.
  • John P. McSorley. Counting structures in the Möbius ladder // Discrete Mathematics. — 1998. — Т. 184, вип. 1–3 (7 лютого). — С. 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 (7 лютого). — С. 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 (7 лютого). — С. 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 (7 лютого). — С. 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 (7 лютого). — С. 3219–3221. — DOI:10.1021/ja00375a051.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.