Драбина Мебіуса

Анімація перетворення одного виду в інший

Подання драбини Мебіуса M₁₆ у вигляді стрічки Мебіуса.

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

Якщо $n \equiv 2 (\mod 4)$ , то $M_{n}$ є двочастковим. При $n \equiv 2 (\mod 4)$ за теоремою Брукса хроматичне число $M_{n}$ дорівнює 3. ВідомоШаблон:Sfn, що драбина Мебіуса однозначно визначається її многочленом Татта.

Властивості

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

Драбини Мебіуса є вершинно-транзитивними, але (за винятком $M_{6}$ ) не реберно-транзитивними — кожне ребро циклу, з якого драбину утворено, належить єдиному 4-реберному циклу, тоді як кожна перекладина належить двом таким циклам.

Драбина Мебіуса $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.

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

Драбини Мебіуса використовують також в інформатиці в межах підходу цілочисельного програмування до задач пакування множин і лінійного впорядкування. Деякі конфігурації в цих задачах можна використати для визначення граней політопів, що описують Шаблон:Не перекладено лінійного програмування. Ці грані називають обмеженнями драбин МебіусаШаблон:Sfn Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn.

Див. також

Примітки

Шаблон:Reflist

Література

Посилання

Шаблон:Mathworld

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

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

[1]

Драбина Мебіуса

Зміст

Властивості

Мінори графа

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

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

Див. також

Примітки

Література

Посилання

Навігаційне меню

Драбина Мебіуса

Властивості

Мінори графа

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

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

Див. також

Примітки

Література

Посилання

Навігаційне меню

Пошук