Граф цикла, в котором все противоположные узлы связаны
В теории графов лестница Мёбиуса M n для чётных чисел n формируется из n -цикла путём добавления рёбер (называемых «ступеньками»), соединяющих противоположные пары вершин в цикле . Это кубический циркулянтный граф , названный так потому, что (за исключением M 6 ( граф полезности K 3,3 ), M n имеет ровно n /2 четырёхциклов [1], которые связаны вместе своими общими рёбрами, образуя топологическую ленту Мёбиуса . Лестницы Мёбиуса были названы и впервые изучены Гаем и Харари (1967).
Характеристики
Для любого четного n > 4 лестница Мёбиуса M n является непланарным графом вершин , что означает, что его нельзя нарисовать без пересечений на плоскости, но удаление одной вершины позволяет нарисовать оставшийся граф без пересечений. Эти графы имеют пересечение номер один и могут быть вложены без пересечений на тор или проективную плоскость . Таким образом, они являются примерами тороидальных графов . Ли (2005) исследует вложения этих графов на поверхности более высокого рода.
Лестницы Мёбиуса являются вершинно-транзитивными – они имеют симметрии, переводящие любую вершину в любую другую вершину – но (за исключением M 4 и M 6 ) они не являются рёберно-транзитивными . Ребра из цикла, из которого образована лестница, можно отличить от перекладин лестницы, потому что каждое ребро цикла принадлежит одному 4-циклу, в то время как каждая перекладина принадлежит двум таким циклам. Следовательно, нет симметрии, переводящей ребро цикла в ребро перекладины или наоборот.
Когда n ≡ 2 (mod 4) , M n является двудольным . Когда n ≡ 0 (mod 4) , он не является двудольным. Конечные точки каждой ступени находятся на четном расстоянии друг от друга в начальном цикле, поэтому добавление каждой ступени создает нечетный цикл. В этом случае, поскольку граф является 3-регулярным, но не двудольным, по теореме Брукса он имеет хроматическое число 3. Де Миер и Ной (2004) показывают, что лестницы Мёбиуса однозначно определяются их полиномами Тутте .
Лестница Мёбиуса M 8 имеет 392 остовных дерева ; она и M 6 имеют наибольшее количество остовных деревьев среди всех кубических графов с одинаковым числом вершин. [2] Однако 10-вершинный кубический граф с наибольшим количеством остовных деревьев — это граф Петерсена , который не является лестницей Мёбиуса.
Лестницы Мёбиуса играют важную роль в теории миноров графов . Самым ранним результатом этого типа является теорема Клауса Вагнера (1937) о том, что графы без миноров K 5 могут быть образованы с помощью операций кликовой суммы для объединения планарных графов и лестницы Мёбиуса M 8 ; по этой причине M 8 называется графом Вагнера .
Губсер (1996) определяет почти планарный граф как непланарный граф, для которого каждый нетривиальный минор является планарным; он показывает, что 3-связные почти планарные графы являются лестницами Мёбиуса или членами небольшого числа других семейств, и что другие почти планарные графы могут быть образованы из них с помощью последовательности простых операций.
Махарри (2000) показывает, что почти все графы, не имеющие кубического минора, могут быть получены с помощью последовательности простых операций из лестниц Мёбиуса.
Химия и физика
Walba, Richards & Haltiwanger (1982) впервые синтезировали молекулярные структуры в форме лестницы Мёбиуса, и с тех пор эта структура представляет интерес для химии и химической стереографии, [4] особенно ввиду лестничной формы молекул ДНК. Имея в виду это приложение, Flapan (1989) изучает математические симметрии вложений лестниц Мёбиуса в R 3 . В частности, как она показывает, каждое трехмерное вложение лестницы Мёбиуса с нечетным числом ступеней является топологически хиральным : его нельзя преобразовать в его зеркальное отображение непрерывной деформацией пространства без прохождения одного края через другое. С другой стороны, лестницы Мёбиуса с четным числом ступеней все имеют вложения в R 3 , которые можно деформировать в их зеркальные отображения.
Лестницы Мёбиуса также использовались в форме сверхпроводящего кольца в экспериментах по изучению влияния топологии проводника на электронные взаимодействия. [5]
Комбинаторная оптимизация
Лестницы Мёбиуса также использовались в информатике как часть подходов целочисленного программирования к проблемам упаковки множеств и линейного упорядочения. Определенные конфигурации в этих задачах могут быть использованы для определения граней многогранника, описывающего релаксацию линейного программирования задачи; эти грани называются ограничениями лестницы Мёбиуса. [6]
^ Мила, Стаффорд и Каппони (1998); Дэн, Сюй и Лю (2002).
^ Болоташвили, Ковалев и Гирлич (1999); Борндорфер и Вейсмантель (2000); Гретшель, Юнгер и Рейнельт (1985a, 1985b); Ньюман и Вемпала (2001)
Ссылки
Биггс, Н. Л.; Дамерелл, Р. М.; Сэндс, Д. А. (1972). «Рекурсивные семейства графов». Журнал комбинаторной теории . Серия B. 12 (2): 123–131. doi : 10.1016/0095-8956(72)90016-0 . MR 0294172.
Болоташвили, Г.; Ковалев, М.; Гирлич, Э. (1999). «Новые грани линейного упорядочения многогранника». SIAM Journal on Discrete Mathematics . 12 (3): 326–336. CiteSeerX 10.1.1.41.8722 . doi :10.1137/S0895480196300145. MR 1710240.
Борндорфер, Ральф; Вайсмантель, Роберт (2000). «Релаксации упаковки множеств некоторых целочисленных программ». Математическое программирование . Серия A. 88 (3): 425–450. doi :10.1007/PL00011381. MR 1782150. S2CID 206862305.
Дэн, Вэнь-Цзи; Сюй, Цзи-Хуань; Лю, Пин (2002). «Уменьшение периода вдвое постоянных токов в мезоскопических лестницах Мёбиуса». Chinese Physics Letters . 19 (7): 988–991. arXiv : cond-mat/0209421 . Bibcode : 2002ChPhL..19..988D. doi : 10.1088/0256-307X/19/7/333. S2CID 119421223.
Махарри, Джон (2000). «Характеристика графов без кубического минора». Журнал комбинаторной теории . Серия B. 80 (2): 179–201. doi : 10.1006/jctb.2000.1968 . MR 1794690.
МакСорли, Джон П. (1998). «Подсчет структур в лестнице Мёбиуса». Дискретная математика . 184 (1–3): 137–164. doi : 10.1016/S0012-365X(97)00086-1 . MR 1609294.
Де Миер, Анна; Ной, Марк (2004). «О графах, определяемых их полиномами Тутте». Графы и комбинаторика . 20 (1): 105–119. doi :10.1007/s00373-003-0534-z. MR 2048553. S2CID 46312268.
Newman, Alantha; Vempala, Santosh (2001). "Fences are futile: on relaxs for the linear ordering problem". Целочисленное программирование и комбинаторная оптимизация: 8-я международная конференция IPCO, Утрехт, Нидерланды, 13–15 июня 2001 г., Труды . Lecture Notes in Computer Science. Vol. 2081. Berlin: Springer-Verlag. pp. 333–347. doi :10.1007/3-540-45535-3_26. MR 2041937. Архивировано из оригинала 2004-01-02 . Получено 2006-10-08 .
Саймон, Джонатан (1992). «Узлы и химия». Новые научные приложения геометрии и топологии (Балтимор, Мэриленд, 1992) . Труды симпозиумов по прикладной математике. Т. 45. Провиденс, Род-Айленд: Американское математическое общество . С. 97–130. MR 1196717.
Вальдес, Л. (1991). «Экстремальные свойства остовных деревьев в кубических графах». Труды Двадцать второй Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Луизиана, 1991) . Congressus Numerantium. Т. 85. С. 143–160. MR 1152127.
Вагнер, К. (1937). «Über eine Eigenschaft der ebenen Komplexe». Математические Аннален . 114 : 570–590. дои : 10.1007/BF01594196. MR 1513158. S2CID 123534907.
Вальба, Д.; Ричардс, Р.; Халтивангер, Р.К. (1982). «Тотальный синтез первой молекулярной ленты Мёбиуса». Журнал Американского химического общества . 104 (11): 3219–3221. дои : 10.1021/ja00375a051.
