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

Лестница Мёбиуса
Два вида лестницы Мёбиуса М 16 . Анимацию, показывающую трансформацию между двумя представлениями, смотрите в этом файле .
Вершины	n (четное число)
Края	п + ⁠ n / 2 ⁠
Обхват	4 (для четного n > 4 )
Хроматическое число	3
Хроматический индекс	3
Род	1 (для четного n > 4 )
Характеристики	Кубический циркулирующий Вершинно-транзитивный Вершина (для четного n > 4 ) Тороидальный (для четных n > 4 ) Крайно-транзитивный (для n = 4, 6 ) Двудольный (для недважды четных n )
Обозначения	М н
Таблица графиков и параметров

В теории графов лестница Мёбиуса Mn _{формируется} для четных чисел n из n - цикла путем добавления ребер (называемых «ступенями»), соединяющих противоположные пары вершин в цикле. Это кубический циркулянтный граф что (за исключением M6 _{, названный так потому ,} ( полезности K3,3 _граф , Mn _{) )} имеет ровно n /2 четырехциклов. которые соединяются общими краями, образуя топологическую ленту Мёбиуса . Лестницы Мёбиуса были названы и впервые изучены Гаем и Харари ( 1967 ).

Характеристики

Для каждого четного n > 4 лестница Мёбиуса M _n представляет собой неплоский вершинный граф , что означает, что ее нельзя нарисовать без пересечений на плоскости, но удаление одной вершины позволяет нарисовать оставшийся граф без пересечений. Эти графы имеют пересечение номер один и могут быть вложены без пересечений на тор или проективную плоскость . Таким образом, они являются примерами тороидальных графов . Ли (2005) исследует встраивание этих графов в поверхности более высокого рода.

Лестницы Мёбиуса вершинно-транзитивны переводящей любую вершину в любую другую вершину – но (за исключением M4 _{– они обладают симметрией} и M6 _, ) они не являются реберно-транзитивными . Ребра цикла, из которого формируется лестница, можно отличить от ступенек лестницы, поскольку каждое ребро цикла принадлежит одному 4-циклу, а каждая ступень принадлежит двум таким циклам. Следовательно, не существует симметрии, переводящей ребро цикла в ребро ступени и наоборот.

Когда n ≡ 2 (mod 4 , M _n двудольный ) . Когда n ≡ 0 (mod 4) он не двудольный. Конечные точки каждой ступени находятся на четном расстоянии друг от друга в начальном цикле, поэтому добавление каждой ступени создает нечетный цикл. В этом случае, поскольку граф является 3-регулярным, но не двудольным, по теореме Брукса он имеет хроматическое число 3. Де Миер и Ной (2004) показывают, что лестницы Мёбиуса однозначно определяются своими полиномами Тутте .

Лестница Мёбиуса М ₈ имеет 392 пролетных дерева ; он и имеют _M6 наибольшее количество остовных деревьев среди всех кубических графов с одинаковым числом вершин. Однако кубический граф с 10 вершинами и наибольшим количеством остовных деревьев — это граф Петерсена , который не является лестницей Мёбиуса.

Полиномы Тутте лестниц Мёбиуса могут быть вычислены с помощью простого рекуррентного соотношения .

Миноры графа

Граф Вагнера М ₈

Лестницы Мёбиуса играют важную роль в теории миноров графов . Самым ранним результатом этого типа является теорема Клауса Вагнера ( 1937 ), согласно которой графы без минора K ₅ могут быть сформированы с помощью операций суммы клик для объединения плоских графов и лестницы Мёбиуса M ₈ ; этой причине М8 _. называется графом Вагнера по

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

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

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

Вальба, Ричардс и Халтивангер (1982) впервые синтезировали молекулярные структуры в форме лестницы Мёбиуса, и с тех пор эта структура представляет интерес в химии и химической стереографии. особенно с учетом лестничной формы молекул ДНК. Имея в виду это приложение, Флапан ( 1989 ) изучает математические симметрии вложений лестниц Мёбиуса в R ³ . В частности, как она показывает, каждое трехмерное вложение лестницы Мёбиуса с нечетным числом ступенек топологически кирально : ее нельзя преобразовать в свое зеркальное отражение путем непрерывной деформации пространства, не проведя одно ребро через другое. С другой стороны, все лестницы Мёбиуса с четным числом ступеней имеют вложения в R. ³ которые можно деформировать в их зеркальные изображения.

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

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

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

См. также

• Лестничная диаграмма
• График призмы

Ссылки

• Биггс, Нидерланды ; Дамерелл, РМ; Сэндс, Д.А. (1972). «Рекурсивные семейства графов» . Журнал комбинаторной теории . Серия Б. 12 (2): 123–131. дои : 10.1016/0095-8956(72)90016-0 . МР   0294172 .
• Болоташвили Г.; Ковалев М.; Гирлич, Э. (1999). «Новые грани многогранника линейного порядка». SIAM Journal по дискретной математике . 12 (3): 326–336. CiteSeerX   10.1.1.41.8722 . дои : 10.1137/S0895480196300145 . МР   1710240 .
• Борндорфер, Ральф; Вейсмантель, Роберт (2000). «Установить ослабление упаковки некоторых целочисленных программ». Математическое программирование . Серия А. 88 (3): 425–450. дои : 10.1007/PL00011381 . МР   1782150 . S2CID   206862305 .
• Дэн, Вэнь-Цзи; Сюй, Цзи-Хуан; Лю, Пин (2002). «Уменьшение периода вдвое постоянных токов в мезоскопических лестницах Мёбиуса». Китайские буквы по физике . 19 (7): 988–991. arXiv : cond-mat/0209421 . Бибкод : 2002ЧФЛ..19..988Д . дои : 10.1088/0256-307X/19/7/333 . S2CID   119421223 .
• Флапан, Эрика (1989). «Симметрия лестниц Мёбиуса». Математические летописи . 283 (2): 271–283. дои : 10.1007/BF01446435 . МР   0980598 . S2CID   119705062 .
• Гретшель, М .; Юнгер, М.; Рейнельт, Г. (1985a). «О многограннике ациклического подграфа». Математическое программирование . 33 : 28–42. дои : 10.1007/BF01582009 . МР   0809747 . S2CID   206798683 .
• Гретшель, М.; Юнгер, М.; Рейнельт, Г. (1985b). «Грани многогранника линейного порядка». Математическое программирование . 33 : 43–60. дои : 10.1007/BF01582010 . МР   0809748 . S2CID   21071064 .
• Губсер, Брэдли С. (1996). «Характеристика почти плоских графов». Комбинаторика, теория вероятностей и вычисления . 5 (3): 227–245. дои : 10.1017/S0963548300002005 . МР   1411084 . S2CID   7313209 .
• Гай, Ричард К .; Харари, Фрэнк (1967). «По лестнице Мёбиуса» . Канадский математический бюллетень . 10 (4): 493–496. дои : 10.4153/CMB-1967-046-4 . МР   0224499 .
• Якобсон Дмитрий; Ривин, Игорь (1999). «О некоторых экстремальных задачах теории графов». arXiv : math.CO/9907050 .
• Ли, Де-мин (2005). «Родовые распределения лестниц Мёбиуса». Северо-восточный математический журнал . 21 (1): 70–80. МР   2124859 .
• Махарри, Джон (2000). «Характеристика графов без минора куба» . Журнал комбинаторной теории . Серия Б. 80 (2): 179–201. дои : 10.1006/jctb.2000.1968 . МР   1794690 .
• МакСорли, Джон П. (1998). «Счет структур в лестнице Мёбиуса» . Дискретная математика . 184 (1–3): 137–164. дои : 10.1016/S0012-365X(97)00086-1 . МР   1609294 .
• Де Мье, Анна; Ной, Марк (2004). «О графиках, определяемых их полиномами Тутте». Графы и комбинаторика . 20 (1): 105–119. дои : 10.1007/s00373-003-0534-z . МР   2048553 . S2CID   46312268 .
• Мила, Фредерик; Стаффорд, Калифорния; Каппони, Сильвен (1998). «Постоянные токи в лестнице Мёбиуса: проверка межцепной когерентности взаимодействующих электронов» (PDF) . Физический обзор B . 57 (3): 1457–1460. arXiv : cond-mat/9705119 . Бибкод : 1998PhRvB..57.1457M . дои : 10.1103/PhysRevB.57.1457 . S2CID   35931632 .
• Ньюман, Аланта; Вемпала, Сантош (2001). «Заборы бесполезны: о релаксациях для задачи линейного упорядочения» . Целочисленное программирование и комбинаторная оптимизация: 8-я Международная конференция IPCO, Утрехт, Нидерланды, 13–15 июня 2001 г., Материалы . Конспекты лекций по информатике. Том. 2081. Берлин: Springer-Verlag. стр. 333–347. дои : 10.1007/3-540-45535-3_26 . МР   2041937 . Архивировано из оригинала 02 января 2004 г. Проверено 8 октября 2006 г.
• Саймон, Джонатан (1992). «Узлы и химия». Новые научные применения геометрии и топологии (Балтимор, Мэриленд, 1992) . Материалы симпозиумов по прикладной математике. Том. 45. Провиденс, Род-Айленд: Американское математическое общество . стр. 97–130. МР   1196717 .
• Вальдес, Л. (1991). «Экстремальные свойства остовных деревьев в кубических графах». Труды двадцать второй Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Луизиана, 1991) . Конгресс Нумерантиум. Том. 85. стр. 143–160. МР   1152127 .
• Вагнер, К. (1937). «О свойстве плоских комплексов». Математические летописи . 114 :570-590. дои : 10.1007/BF01594196 . МР1513158   . S2CID   123534907 .
• Вальба, Д.; Ричардс, Р.; Халтивангер, Р.К. (1982). «Тотальный синтез первой молекулярной ленты Мёбиуса». Журнал Американского химического общества . 104 (11): 3219–3221. дои : 10.1021/ja00375a051 .

Внешние ссылки

• Вайсштейн, Эрик В. «Лестница Мёбиуса» . Математический мир .