Loading AI tools
кубический циркулянтный граф Из Википедии, свободной энциклопедии
Ле́стница Мёбиуса — кубический циркулянтный граф с чётным числом вершин , образованный из цикла с вершинами путём добавления рёбер (называемых «перекладинами»), соединяющих противоположные пары вершин цикла. Назван так ввиду того, что состоит из циклов длины 4[1], соединённых вместе общими рёбрами и образующих топологически ленту Мёбиуса. Полный двудольный граф (граф «домики и колодцы») является лестницей Мёбиуса (в отличие от остальных имеет дополнительные циклы длины 4).
Любая лестница Мёбиуса является непланарным верхушечнным графом. Число скрещиваний лестницы Мёбиуса равно единице, и граф может быть вложен без самопересечений в тор или проективную плоскость (то есть является тороидальным графом). Ли[3] изучил вложение этих графов в поверхности более высоких родов.
Лестницы Мёбиуса являются вершинно-транзитивными, но (за исключением ) не рёберно-транзитивными — каждое ребро цикла, из которого лестница образована, принадлежит единственному 4-рёберному циклу, в то время как каждая перекладина принадлежит двум таким циклам.
Если , то является двудольным. При по теореме Брукса хроматическое число равно 3. Известно[4], что лестница Мёбиуса однозначно определяется её многочленом Татта.
Лестница Мёбиуса имеет 392 остовных дерева. Этот граф и имеют наибольшее число остовных деревьев среди кубических графов с тем же числом вершин[5][6]. Однако среди кубических графов с 10 вершинами наибольшее число остовных деревьев у графа Петерсена, который не является лестницей Мёбиуса.
Многочлены Татта лестниц Мёбиуса можно получить по простой рекуррентной формуле[7].
Лестницы Мёбиуса играют важную роль в теории миноров графа. Самым ранним результатом такого типа является теорема Вагнера[8] о том, что граф, не содержащий -миноров, может быть образован с использованием сумм по клике для комбинирования планарных графов и лестницы Мёбиуса (в этой связи называют графом Вагнера.
Все 3-связные почти-планарные графы[9] являются лестницами Мёбиуса или принадлежат небольшому числу других семейств, притом остальные почти-планарные графы можно получить из этих графов с помощью ряда простых операций[10].
Почти все[уточнить] графы, не содержащие куб в качестве минора, могут быть получены из лестниц Мёбиуса в результате последовательного применения простых операций[11].
В 1982 году синтезирована молекулярная структура, имеющую форму лестницы Мёбиуса[12], и с тех пор такие графы представляют интерес для химиков и химической стереографии[13], особенно в свете похожих на лестницу Мёбиуса молекул ДНК. Имея это в виду, особо изучены математические симметрии вложений лестниц Мёбиуса в [14].
Лестницы Мёбиуса используются как модель сверхпроводимого кольца в экспериментах по изучению эффектов топологии проводимости при взаимодействии электронов[15][16].
Лестницы Мёбиуса используются также в информатике как часть подхода целочисленного программирования к задачам упаковки множеств и линейного упорядочивания. Некоторые конфигурации в этих задачах могут быть использованы для определения граней политопов, описывающих ослабление условий[англ.] линейного программирования. Эти грани называются ограничениями лестниц Мёбиуса[17][18][19][20].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
