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

Лестница Мёбиуса M n {displaystyle M_{n}} — кубический циркулянтный граф с чётным числом вершин n {displaystyle n} , образованный из цикла с n {displaystyle n} вершинами путём добавления рёбер (называемых «перекладинами»), соединяющих противоположные пары вершин цикла. Назван так ввиду того, что M n {displaystyle M_{n}} состоит из n / 2 {displaystyle n/2} циклов длины 4, соединённых вместе общими рёбрами и образующих топологически ленту Мёбиуса. Полный двудольный граф K 3 , 3 {displaystyle K_{3,3}} (граф «домики и колодцы») является лестницей Мёбиуса M 6 {displaystyle M_{6}} (в отличие от остальных M 6 {displaystyle M_{6}} имеет дополнительные циклы длины 4).

Впервые изучены Гаем и Харари.

Свойства

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

Лестницы Мёбиуса являются вершинно-транзитивными, но (за исключением M 6 {displaystyle M_{6}} ) не рёберно-транзитивными — каждое ребро цикла, из которого лестница образована, принадлежит единственному 4-рёберному циклу, в то время как каждая перекладина принадлежит двум таким циклам.

Если n ≡ 2 ( mod 4 ) {displaystyle nequiv 2{pmod {4}}} , то M n {displaystyle M_{n}} является двудольным. При n ≡ 2 ( mod 4 ) {displaystyle nequiv 2{pmod {4}}} по теореме Брукса хроматическое число M n {displaystyle M_{n}} равно 3. Известно, что лестница Мёбиуса однозначно определяется её многочленом Татта.

Лестница Мёбиуса M 8 {displaystyle M_{8}} имеет 392 остовных дерева. Этот граф и M 6 {displaystyle M_{6}} имеют наибольшее число остовных деревьев среди кубических графов с тем же числом вершин. Однако среди кубических графов с 10 вершинами наибольшее число остовных деревьев у графа Петерсена, который не является лестницей Мёбиуса.

Многочлены Татта лестниц Мёбиуса можно получить по простой рекуррентной формуле.

Миноры графа

Лестницы Мёбиуса играют важную роль в теории миноров графа. Самым ранним результатом такого типа является теорема Вагнера о том, что граф, не содержащий K 5 {displaystyle K_{5}} -миноров, может быть образован с использованием сумм по клике для комбинирования планарных графов и лестницы Мёбиуса M 8 {displaystyle M_{8}} (в этой связи M n {displaystyle M_{n}} называют графом Вагнера.

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

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

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

В 1982 году синтезирована молекулярная структура, имеющую форму лестницы Мёбиуса, и с тех пор такие графы представляют интерес для химиков и химической стереографии, особенно в свете похожих на лестницу Мёбиуса молекул ДНК. Имея это в виду, особо изучены математические симметрии вложений лестниц Мёбиуса в R 3 {displaystyle mathbb {R} ^{3}} .

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

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

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