WikiDer > Система вращения

В комбинаторный математика, системы вращения (также называемый комбинаторные вложения) кодируют вложения графики на ориентируемый поверхности, описывая круговой заказ ребер графа вокруг каждой вершины. Более формальное определение системы вращения включает в себя пары перестановок; такой пары достаточно, чтобы определить мультиграф, поверхность и 2-ячеечное вложение мультиграфа на поверхность.

Каждая схема вращения определяет уникальное двухклеточное вложение связного мультиграфа на замкнутую ориентированную поверхность (с точностью до сохраняющей ориентацию топологической эквивалентности). Наоборот, любое вложение связного мультиграфа грамм на ориентированной замкнутой поверхности определяет уникальную систему вращения, имеющую грамм как лежащий в основе мультиграф. Эта фундаментальная эквивалентность между системами вращения и вложениями из двух ячеек была впервые установлена ​​в двойной форме Хеффтером и широко использовалась Рингель в течение 1950-х гг. Независимо, Эдмондс дал первоначальную форму теоремы, а детали его исследования были популяризированы Янгсом. Обобщение на весь набор мультиграфов было разработано Гроссом и Альпертом.

Системы ротации связаны, но не одинаковы с карты вращения используется Reingold et al. (2002), чтобы определить зигзагообразный продукт графиков. Система вращения определяет круговой порядок ребер вокруг каждой вершины, тогда как карта вращения определяет (некруглую) перестановку ребер в каждой вершине. Кроме того, системы вращения могут быть определены для любого графа, в то время как, как Reingold et al. определить их карты вращения ограничены регулярные графики.

Формальное определение

Формально система вращения определяется как пара (σ, θ), где σ и θ - перестановки, действующие на одном и том же основном множестве B, θ - свободная от неподвижной точки инволюция, а группа <σ,θ> генерируется через σ и θ действует транзитивно на B.

Чтобы вывести систему вращения из двухклеточного вложения связного мультиграфа грамм на ориентированной поверхности пусть B состоит из дартс (или же флаги, или же полуребра) из грамм; то есть для каждого края грамм мы формируем два элемента B, по одному на каждую конечную точку ребра. Даже когда ребро имеет ту же вершину, что и обе его конечные точки, мы создаем для этого ребра два дротика. Пусть θ (б) - другой дротик, образованный из того же края, что и б; это явно инволюция без неподвижных точек. Пусть σ (б) быть дротиком по часовой стрелке от б в циклическом порядке ребер, инцидентных одной и той же вершине, где «по часовой стрелке» определяется ориентацией поверхности.

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

Восстановление вложения из ротационной системы

Чтобы восстановить мультиграф из системы вращения, мы формируем вершину для каждой орбиты σ и ребро для каждой орбиты θ. Вершина инцидентна ребру, если эти две орбиты имеют непустое пересечение. Таким образом, количество инцидентов на вершину - это размер орбиты, а количество инцидентов на ребро равно ровно двум. Если система вращения получена из 2-ячеечного вложения связного мультиграфа грамм, граф, полученный из системы вращения, изоморфен грамм.

Чтобы встроить граф, полученный из системы вращения, на поверхность, сформируйте диск для каждой орбиты σθ и склейте два диска вдоль ребра е когда два дротика, соответствующие е принадлежат двум орбитам, соответствующим этим дискам. Результатом является вложение производного мультиграфа с двумя ячейками, две ячейки которого представляют собой диски, соответствующие орбитам σθ. Поверхность этого вложения может быть ориентирована таким образом, что порядок ребер по часовой стрелке вокруг каждой вершины такой же, как порядок по часовой стрелке, задаваемый σ.

Характеристика поверхности вложения

Согласно Формула Эйлера мы можем вывести род грамм замкнутой ориентируемой поверхности, определяемой системой вращения ${ Displaystyle ( sigma, theta)}$ (то есть поверхность, на которой базовый мультиграф состоит из двух ячеек).^[1] Заметь ${ Displaystyle V = | Z ( sigma) |}$, ${ Displaystyle Е = | Z ( тета) |}$ и ${ Displaystyle F = | Z ( sigma theta) |}$. Мы находим, что

${ displaystyle g = 1 - { frac {1} {2}} (V-E + F) = 1 - { frac {1} {2}} (| Z ( sigma) | - | Z ( тета) | + | Z ( сигма тета) |)}$

куда ${ Displaystyle Z ( phi)}$ обозначает множество орбит перестановки ${ displaystyle phi}$.

Смотрите также

• Комбинаторная карта

Примечания

Рекомендации

• Р. Кори и А. Маши (1992). «Карты, гиперкарты и их автоморфизмы: обзор». Expositiones Mathematicae. 10: 403–467. МИСТЕР 1190182.CS1 maint: ref = harv (связь)
• Дж. Эдмондс (1960). «Комбинаторное представление для многогранных поверхностей». Уведомления Американского математического общества. 7: 646.CS1 maint: ref = harv (связь)
• Дж. Л. Гросс и С. Р. Альперт (1974). «Топологическая теория текущих графов». Журнал комбинаторной теории, серия B. 17 (3): 218–233. Дои:10.1016/0095-8956(74)90028-8. МИСТЕР 0363971.CS1 maint: ref = harv (связь)
• Л. Хеффтер (1891). "Über das Problem der Nachbargebiete". Mathematische Annalen. 38 (4): 477–508. Дои:10.1007 / BF01203357. S2CID 121206491.CS1 maint: ref = harv (связь)
• Ландо, Сергей К .; Звонкин, Александр К. (2004). Графы на поверхностях и их приложения. Энциклопедия математических наук: низкоразмерная топология II. 141. Берлин, Нью-Йорк: Springer-Verlag. ISBN 978-3-540-00203-1.CS1 maint: ref = harv (связь).
• Боян Мохар и Карстен Томассен (2001). Графики на поверхностях. Издательство Университета Джона Хопкинса. ISBN 0-8018-6689-8.
• О. Рейнгольд; С. Вадхан и А. Вигдерсон (2002). «Энтропийные волны, зигзагообразный граф и новые расширители постоянной степени». Анналы математики. 155 (1): 157–187. arXiv:математика / 0406038. Дои:10.2307/3062153. JSTOR 3062153. МИСТЕР 1888797. S2CID 120739405.CS1 maint: ref = harv (связь)
• Г. Рингель (1965). "Das Geschlecht des vollständigen paaren Graphen". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 28 (3–4): 139–150. Дои:10.1007 / BF02993245. МИСТЕР 0189012. S2CID 120414651.CS1 maint: ref = harv (связь)
• Дж. У. Т. Янгс (1963). «Минимальные вложения и род графа». Журнал математики и механики. 12 (2): 303–315. Дои:10.1512 / iumj.1963.12.12021. МИСТЕР 0145512.CS1 maint: ref = harv (связь)