Ле́стница Мёбиуса — кубический циркулянтный граф с чётным числом вершин , образованный из цикла с вершинами путём добавления рёбер (называемых перекладинами), соединяющих противоположные пары вершин цикла. Назван так ввиду того, что состоит из циклов длины 4, соединённых вместе общими рёбрами и образующих топологическую известную ленту Мёбиуса. Полный двудольный граф (граф «домики и колодцы») является лестницей Мёбиуса (в отличие от остальных имеет дополнительные циклы длины 4).
Впервые изучены Ричардом Гаем и Фрэнком Харари. В теории узлов лестница Мёбиуса рассматривается как граф, вложения которого в трёхмерное пространство образуют зацепления; структура $M_{2n}$ эквивалентна проекции перекрученного узла типа $(2, n)$ .
Свойства Любая лестница Мёбиуса является непланарным верхушечнным графом. Число скрещиваний лестницы Мёбиуса равно единице, и граф может быть вложен без самопересечений в тор или проективную плоскость (то есть является тороидальным графом). Ли изучил вложение этих графов в поверхности более высоких родов.
Лестницы Мёбиуса являются вершинно-транзитивными, но (за исключением ) не рёберно-транзитивными — каждое ребро цикла, из которого лестница образована, принадлежит единственному 4-рёберному циклу, в то время как каждая перекладина принадлежит двум таким циклам.
Если , то является двудольным. При по теореме Брукса хроматическое число равно 3. Собственные числа $M_n$ определяются формулой $\lambda_j = 2\cos(2\pi j/n) + (-1)^j$ для $j=0, 1, \dots, n-1$ .Известно, что лестница Мёбиуса однозначно определяется её многочленом Татта.
Лестница Мёбиуса имеет 392 остовных дерева. Этот граф и имеют наибольшее число остовных деревьев среди кубических графов с тем же числом вершин. Однако, среди кубических графов с 10 вершинами наибольшее число остовных деревьев у графа Петерсена, который не является лестницей Мёбиуса.
Многочлены Татта лестниц Мёбиуса можно получить по простой рекуррентной формуле.
Миноры графа
Лестницы Мёбиуса играют важную роль в теории миноров графа. Самым ранним результатом такого типа является теорема Вагнера о том, что граф, не содержащий -миноров, может быть образован с использованием сумм по клике для комбинирования планарных графов и лестницы Мёбиуса (в этой связи называют графом Вагнера).
Все 3-связные, почти-планарные графыПочти-планарный граф — непланарный граф, у которого любой нетривиальный минор планарен являются лестницами Мёбиуса или принадлежат небольшому числу других семейств, притом остальные почти-планарные графы можно получить из этих графов с помощью ряда простых операций.
Почти все графы, не содержащие куб в качестве минора, могут быть получены из лестниц Мёбиуса в результате последовательного применения простых операций.
Химия и физика В 1982 году синтезирована молекулярная структура, имеющую форму лестницы Мёбиуса, и с тех пор такие графы представляют интерес для химиков и химической стереографии, особенно в свете похожих на лестницу Мёбиуса молекул ДНК. Имея это в виду, особо изучены математические симметрии вложений лестниц Мёбиуса в .
Лестницы Мёбиуса используются как модель сверхпроводимого кольца в экспериментах по изучению эффектов топологии проводимости при взаимодействии электронов. В нанотехнологиях структура $M_n$ применяется для моделирования электронных состояний графеновых нанолент с однократным перекручиванием, где топология Мёбиуса определяет размер энергетической щели .
Комбинаторная оптимизация Лестницы Мёбиуса используются также в информатике как часть подхода целочисленного программирования к задачам упаковки множеств и линейного упорядочивания. Некоторые конфигурации в этих задачах могут быть использованы для определения граней политопов, описывающих линейного программирования. Эти грани называются ограничениями лестниц Мёбиуса.
См. также Лента Мёбиуса
Бутылка Клейна Граф-лестница
Примечания
Литература
Ссылки
Категория:Регулярные графы Категория:Параметрические семейства графов