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

Два представления лестницы Мёбиуса $M_{16}$ .

Анимация преобразования одного вида в другой

Представление лестницы Мёбиуса M₁₆ в виде ленты Мёбиуса.

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

Впервые изучены Гаем и Харари Шаблон:Sfn.

Свойства

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

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

Если $n \equiv 2 (\mod 4)$ , то $M_{n}$ является двудольным. При $n \equiv 2 (\mod 4)$ по теореме Брукса хроматическое число $M_{n}$ равно 3. ИзвестноШаблон:Sfn, что лестница Мёбиуса однозначно определяется её многочленом Татта.

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

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

Миноры графа

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

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

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

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

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

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

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Mathworld

Шаблон:Rq

↑ Почти-планарный граф — непланарный граф, у которого любой нетривиальный минор планарен

[1] Почти-планарный граф — непланарный граф, у которого любой нетривиальный минор планарен

[1]

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

Содержание

Свойства

Миноры графа

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

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

См. также

Примечания

Литература

Ссылки

Навигация

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

Свойства

Миноры графа

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

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

См. также

Примечания

Литература

Ссылки

Навигация

Поиск