В теории графов , то Мёбиусова лестница М п является кубическим циркулянтом графа с четным числом п вершин, образованным из п - цикл добавления ребер ( так называемый «ступеньку») , соединяющей противоположные пары вершин в цикле. Он назван так потому, что (за исключением M 6 = K 3,3 ) M n имеет ровно n / 2 4-циклов [1], которые соединяются вместе своими общими ребрами, образуя топологическую ленту Мёбиуса . Лестницы Мебиуса были названы и впервые изучены Гаем.и Харари ( 1967 ).
Характеристики
Каждая лестница Мёбиуса является неплоским графом с вершинами , что означает, что ее нельзя нарисовать без пересечений на плоскости, но удаление одной вершины позволяет нарисовать оставшийся граф без пересечений. Лестницы Мебиуса имеют пересечение номер один и могут быть вложены без пересечений на торе или проективной плоскости . Таким образом, они являются примерами тороидальных графов . Ли (2005) исследует вложения этих графов на поверхности более высокого рода.
Лестницы Мебиуса являются вершинно-транзитивными - у них есть симметрии, переводящие любую вершину в любую другую вершину, но (опять же, за исключением M 6 ) они не являются реберно-транзитивными . Ребра цикла, из которого формируется лестница, можно отличить от ступенек лестницы, потому что каждое ребро цикла принадлежит одному 4-циклу, в то время как каждая ступень принадлежит двум таким циклам. Следовательно, не существует симметрии, переводящей ребро цикла в ребро ступени или наоборот.
При п ≡ 2 ( по модулю 4) , М п является двудольным . Когда n ≡ 0 (mod 4) , он не является двудольным. Конечные точки каждой ступени находятся на четном расстоянии друг от друга в начальном цикле, поэтому добавление каждой ступени создает нечетный цикл. В этом случае, поскольку граф является 3-регулярным, но не двудольным, по теореме Брукса он имеет хроматическое число 3. Де Майер и Ной (2004) показывают, что лестницы Мебиуса однозначно определяются своими полиномами Тутте .
Лестница Мебиуса M 8 имеет 392 опорных дерева ; он и M 6 имеют самые остовные деревья среди всех кубических графов с одинаковым числом вершин. [2] Однако кубический граф с 10 вершинами с наибольшим количеством остовных деревьев - это граф Петерсена , который не является лестницей Мёбиуса.
Эти многочлены TUTTE из лестниц Мёбиуса может быть вычислены с помощью простого рекуррентного соотношения . [3]
График миноров
Лестницы Мебиуса играют важную роль в теории миноров графов . Самым ранним результатом этого типа является теорема Клауса Вагнера ( 1937 ) о том, что графы без минора K 5 могут быть сформированы путем использования операций кликовой суммы для объединения плоских графов и лестницы Мёбиуса M 8 ; по этой причине M 8 называется графом Вагнера .
Губсер (1996) определяет почти планарный граф как непланарный граф, для которого каждый нетривиальный минор является плоским; он показывает, что трехсвязные почти плоские графы являются лестницами Мебиуса или членами небольшого числа других семейств, и что другие почти планарные графы могут быть сформированы из них с помощью последовательности простых операций.
Махарри (2000) показывает, что почти все графы, не имеющие минорного куба, могут быть получены с помощью последовательности простых операций из лестниц Мебиуса.
Химия и физика
Walba, Richards и Haltiwanger (1982) впервые синтезировали молекулярные структуры в форме лестницы Мебиуса, и с тех пор эта структура представляет интерес в химии и химической стереографии [4], особенно с учетом лестничной формы молекул ДНК. . Имея в виду это приложение, Флапан ( 1989 ) изучает математические симметрии вложений лестниц Мебиуса в R 3 . В частности, как она показывает, любое трехмерное вложение лестницы Мёбиуса с нечетным числом ступенек является топологически киральным : его нельзя преобразовать в свое зеркальное отображение путем непрерывной деформации пространства, не пропуская одно ребро через другое. С другой стороны, все лестницы Мебиуса с четным числом ступенек имеют вложения в R 3, которые можно деформировать в их зеркальное отображение.
Лестницы Мебиуса также использовались в качестве формы сверхпроводящего кольца в экспериментах по изучению влияния топологии проводника на взаимодействие электронов. [5]
Комбинаторная оптимизация
Лестницы Мебиуса также использовались в информатике как часть подходов к целочисленному программированию для решения задач упаковки множеств и линейного упорядочения. Определенные конфигурации в рамках этих задач могут использоваться для определения граней многогранника, описывающего релаксацию задачи линейным программированием ; эти фасеты называются лестничными ограничениями Мёбиуса. [6]
Смотрите также
- Лестничный график
- График призмы
Заметки
- ^ МакСорли (1998) .
- ^ Якобсон и Ривин (1999) ; Вальдес (1991) .
- ^ Биггс, Дамереллы & Sands (1972) .
- ↑ Саймон (1992) .
- ^ Мила, Стаффорд и Каппони (1998) ; Дэн, Сюй и Лю (2002) .
- ^ Bolotashvili, Ковалев & Girlich (1999) ; Borndörfer & Weismantel (2000) ; Грётшель, Юнгер и Райнельт ( 1985a , 1985b ); Ньюман и Вемпала (2001)
Рекомендации
- Биггс, Нидерланды ; Дамерелл, РМ; Пески, Д.А. (1972). «Рекурсивные семейства графов» . Журнал комбинаторной теории . Серия Б. 12 (2): 123–131. DOI : 10.1016 / 0095-8956 (72) 90016-0 . Руководство по ремонту 0294172 .
- Болоташвили, Г .; Ковалев, М .; Гирлич, Э. (1999). «Новые грани многогранника линейного порядка». Журнал СИАМ по дискретной математике . 12 (3): 326–336. CiteSeerX 10.1.1.41.8722 . DOI : 10,1137 / S0895480196300145 . Руководство по ремонту 1710240 .
- Борндёрфер, Ральф; Вайсмантель, Роберт (2000). «Установить расслабления упаковки некоторых целочисленных программ». Математическое программирование . Серия А. 88 (3): 425–450. DOI : 10.1007 / PL00011381 . Руководство по ремонту 1782150 . S2CID 206862305 .
- Дэн, Вэнь-Цзи; Сюй, Цзи-Хуань; Лю, Пинг (2002). «Уменьшение периода постоянных токов вдвое в мезоскопических лестницах Мебиуса». Письма китайской физики . 19 (7): 988–991. arXiv : cond-mat / 0209421 . Bibcode : 2002ChPhL..19..988D . DOI : 10,1088 / 0256-307X / 19 / 7/333 . S2CID 119421223 .
- Флапан, Эрика (1989). «Симметрии лестниц Мебиуса». Mathematische Annalen . 283 (2): 271–283. DOI : 10.1007 / BF01446435 . Руководство по ремонту 0980598 . S2CID 119705062 .
- Grötschel, M .; Юнгер, М .; Райнелт, Г. (1985a). «Об ациклическом многограннике подграфов». Математическое программирование . 33 : 28–42. DOI : 10.1007 / BF01582009 . Руководство по ремонту 0809747 . S2CID 206798683 .
- Grötschel, M .; Юнгер, М .; Райнелт, Г. (1985b). «Грани многогранника линейного упорядочения». Математическое программирование . 33 : 43–60. DOI : 10.1007 / BF01582010 . Руководство по ремонту 0809748 . S2CID 21071064 .
- Губсер, Брэдли С. (1996). «Характеристика почти плоских графов». Комбинаторика, теория вероятностей и вычисления . 5 (3): 227–245. DOI : 10.1017 / S0963548300002005 . Руководство по ремонту 1411084 .
- Гай, Ричард К .; Харари, Фрэнк (1967). «По лестницам Мебиуса». Канадский математический бюллетень . 10 (4): 493–496. DOI : 10,4153 / CMB-1967-046-4 . Руководство по ремонту 0224499 .
- Якобсон, Дмитрий; Ривин, Игорь (1999). «О некоторых экстремальных задачах теории графов» . arXiv : math.CO/9907050 . Цитировать журнал требует
|journal=
( помощь ) - Ли, Деминг (2005). «Родовые распределения лестниц Мебиуса». Северо-восточный математический журнал . 21 (1): 70–80. Руководство по ремонту 2124859 .
- Махарри, Джон (2000). «Характеристика графов без минора куба» . Журнал комбинаторной теории . Серия Б. 80 (2): 179–201. DOI : 10.1006 / jctb.2000.1968 . Руководство по ремонту 1794690 .
- МакСорли, Джон П. (1998). «Счетные конструкции в лестнице Мёбиуса» . Дискретная математика . 184 (1–3): 137–164. DOI : 10.1016 / S0012-365X (97) 00086-1 . Руководство по ремонту 1609294 .
- Де Миер, Анна; Ной, Марк (2004). «О графах, определяемых их многочленами Тутте». Графы и комбинаторика . 20 (1): 105–119. DOI : 10.1007 / s00373-003-0534-z . Руководство по ремонту 2048553 . S2CID 46312268 .
- Мила, Фредерик; Стаффорд, Калифорния; Каппони, Сильвен (1998). «Постоянные токи в лестнице Мёбиуса: тест межцепочечной когерентности взаимодействующих электронов» (PDF) . Physical Review B . 57 (3): 1457–1460. arXiv : cond-mat / 9705119 . Bibcode : 1998PhRvB..57.1457M . DOI : 10.1103 / PhysRevB.57.1457 . S2CID 35931632 .
- Ньюман, Аланта; Вемпала, Сантош (2001). «Заборы бесполезны: об ослаблении решения линейной задачи упорядочения» . Целочисленное программирование и комбинаторная оптимизация: 8-я Международная конференция IPCO, Утрехт, Нидерланды, 13–15 июня 2001 г., Труды . Конспект лекций по информатике. 2081 . Берлин: Springer-Verlag. С. 333–347. DOI : 10.1007 / 3-540-45535-3_26 . Руководство по ремонту 2041937 . Архивировано из оригинала на 2004-01-02 . Проверено 8 октября 2006 .
- Саймон, Джонатан (1992). «Узлы и химия». Новые научные приложения геометрии и топологии (Балтимор, Мэриленд, 1992) . Материалы симпозиумов по прикладной математике. 45 . Провиденс, Род-Айленд: Американское математическое общество . С. 97–130. Руководство по ремонту 1196717 .
- Вальдес, Л. (1991). «Экстремальные свойства остовных деревьев в кубических графах». Труды Двадцать второй Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Лос-Анджелес, 1991) . Congressus Numerantium. 85 . С. 143–160. Руководство по ремонту 1152127 .
- Вагнер, К. (1937). "Über eine Eigenschaft der ebenen Komplexe". Mathematische Annalen . 114 : 570–590. DOI : 10.1007 / BF01594196 . Руководство по ремонту 1513158 . S2CID 123534907 .
- Walba, D .; Richards, R .; Халтивангер, Р. К. (1982). «Полный синтез первой молекулярной ленты Мебиуса». Журнал Американского химического общества . 104 (11): 3219–3221. DOI : 10.1021 / ja00375a051 .
Внешние ссылки
- Вайсштейн, Эрик В. «Лестница Мебиуса» . MathWorld .