Системы вращений: комбинаторные вложения и отображения на поверхностях.
Rotation system
Ротационные системы в комбинаторике: кодирование графов на ориентируемых поверхностях через перестановки. Связь с 2-клеточными вложениями и теоремой Хефтера-Рингеля.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В комбинаторной математике системы вращения (также называемые комбинаторными вложениями или комбинаторными картами) кодируют вложения графов на ориентируемые поверхности, описывая циклическую последовательность рёбер графа вокруг каждой вершины. Более формальное определение системы вращения включает пары перестановок; такой пары достаточно для определения мультиграфа, поверхности и вложения двух ячеек мультиграфа на поверхность. Каждая схема вращения определяет единственное вложение двух ячеек связного мультиграфа на замкнутой ориентированной поверхности (с точностью до топологической эквивалентности, сохраняющей ориентацию). Обратно, любое вложение связного мультиграфа G на ориентированной замкнутой поверхности определяет единственную систему вращения, имеющую G в качестве своего базового мультиграфа. Это фундаментальное соответствие между системами вращения и вложениями двух ячеек впервые было установлено в двойственной форме Лотаром Хефтером в 1890-х годах и широко использовалось Рингелем в 1950-х годах. Независимо от этого, Эдмондс дал прямую форму теоремы, а детали его исследования были популяризированы Юнгсом. Обобщение на мультиграфы было представлено Гроссом и Альпертом. Системы вращения связаны с, но не идентичны, картам вращения, используемым Reingold et al. (2002) для определения зигзагообразного произведения графов. Система вращения задаёт циклическую последовательность рёбер вокруг каждой вершины, в то время как карта вращения задаёт (нециклическую) перестановку рёбер в каждой вершине. Кроме того, системы вращения могут быть определены для любого графа, в то время как карты вращения, определяемые Reingold et al., ограничены регулярными графами.
In combinatorial mathematics, rotation systems (also called combinatorial embeddings or combinatorial maps) encode embeddings of graphs onto orientable surfaces by describing the circular ordering of a graph's edges around each vertex. A more formal definition of a rotation system involves pairs of permutations; such a pair is sufficient to determine a multigraph, a surface, and a 2 cell embedding of the multigraph onto the surface. Every rotation scheme defines a unique 2 cell embedding of a connected multigraph on a closed oriented surface (up to orientation preserving topological equivalence). Conversely, any embedding of a connected multigraph G on an oriented closed surface defines a unique rotation system having G as its underlying multigraph. This fundamental equivalence between rotation systems and 2 cell embeddings was first settled in a dual form by Lothar Heffter in the 1890s and extensively used by Ringel during the 1950s. Independently, Edmonds gave the primal form of the theorem and the details of his study have been popularized by Youngs. The generalization to multigraphs was presented by Gross and Alpert. Rotation systems are related to, but not the same as, the rotation maps used by Reingold et al. (2002) to define the zig zag product of graphs. A rotation system specifies a circular ordering of the edges around each vertex, while a rotation map specifies a (non circular) permutation of the edges at each vertex. In addition, rotation systems can be defined for any graph, while as Reingold et al. define them rotation maps are restricted to regular graphs.
Формальное определение
Формально система вращения определяется как пара (σ, θ), где σ и θ – перестановки, действующие на одном и том же базовом множестве B, θ – свободная от неподвижных точек инволюция, а группа <σ, θ>, порожденная σ и θ, действует транзитивно на B. Чтобы получить систему вращения из 2-клеточного вложения связного мультиграфа G на ориентированной поверхности, пусть B состоит из ребер (или флагов, или полуребер) G; то есть для каждого ребра G мы формируем два элемента B, по одному для каждой конечной точки ребра. Даже если у ребра совпадают обе конечные точки, мы создаем два ребра для этого ребра. Пусть θ(b) будет другим ребром, образованным из того же ребра, что и b; это очевидно инволюция без неподвижных точек. Пусть σ(b) будет ребром, расположенным по часовой стрелке от b в циклическом порядке ребер, инцидентных одной и той же вершине, где "по часовой стрелке" определяется ориентацией поверхности. Если мультиграф вложен в ориентируемую, но не ориентированную поверхность, он обычно соответствует двум системам вращения, по одной для каждой из двух ориентаций поверхности. Эти две системы вращения имеют одинаковую инволюцию θ, но перестановка σ для одной системы вращения является обратной соответствующей перестановке для другой системы вращения.
Formally, a rotation system is defined as a pair (σ, θ) where σ and θ are permutations acting on the same ground set B, θ is a fixed point free involution, and the group <σ, θ> generated by σ and θ acts transitively on B. To derive a rotation system from a 2 cell embedding of a connected multigraph G on an oriented surface, let B consist of the darts (or flags, or half edges) of G; that is, for each edge of G we form two elements of B, one for each endpoint of the edge. Even when an edge has the same vertex as both of its endpoints, we create two darts for that edge. We let θ(b) be the other dart formed from the same edge as b; this is clearly an involution with no fixed points. We let σ(b) be the dart in the clockwise position from b in the cyclic order of edges incident to the same vertex, where "clockwise" is defined by the orientation of the surface. If a multigraph is embedded on an orientable but not oriented surface, it generally corresponds to two rotation systems, one for each of the two orientations of the surface. These two rotation systems have the same involution θ, but the permutation σ for one rotation system is the inverse of the corresponding permutation for the other rotation system.
Восстановление встраивания из системы вращения
Чтобы восстановить мультиграф из системы вращений, мы формируем вершину для каждой орбиты σ и ребро для каждой орбиты θ. Вершина инцидентна ребру, если эти две орбиты имеют непустое пересечение. Таким образом, число инциденций для каждой вершины равно размеру её орбиты, а число инциденций для каждого ребра равно ровно двум. Если система вращений получена из 2-клеточного вложения связного мультиграфа G, то мультиграф, полученный из системы вращений, изоморфен G.
To recover a multigraph from a rotation system, we form a vertex for each orbit of σ, and an edge for each orbit of θ. A vertex is incident with an edge if these two orbits have a nonempty intersection. Thus, the number of incidences per vertex is the size of the orbit, and the number of incidences per edge is exactly two. If a rotation system is derived from a 2 cell embedding of a connected multigraph G, the graph derived from the rotation system is isomorphic to G.
Для вложения мультиграфа, полученного из системы вращений, на поверхность, формируем диск для каждой орбиты σθ и склеиваем два диска вдоль ребра e, когда два дротика, соответствующие e, принадлежат двум орбитам, соответствующим этим дискам. В результате получается 2-клеточное вложение полученного мультиграфа, две ячейки которого – диски, соответствующие орбитам σθ. Поверхность этого вложения можно ориентировать таким образом, чтобы порядок обхода рёбер вокруг каждой вершины по часовой стрелке совпадал с порядком, заданным σ.
To embed the graph derived from a rotation system onto a surface, form a disk for each orbit of σθ, and glue two disks together along an edge e whenever the two darts corresponding to e belong to the two orbits corresponding to these disks. The result is a 2 cell embedding of the derived multigraph, the two cells of which are the disks corresponding to the orbits of σθ. The surface of this embedding can be oriented in such a way that the clockwise ordering of the edges around each vertex is the same as the clockwise ordering given by σ.
Характеристика поверхности встраивания
Согласно формуле Эйлера мы можем определить род g замкнутой ориентируемой поверхности, заданной системой вращений (то есть поверхность, на которой базовый мультиграф вкладывается в 2-ячейки). Заметим, что , и мы находим, что
According to the Euler formula we can deduce the genus g of the closed orientable surface defined by the rotation system (that is, the surface on which the underlying multigraph is 2 cell embedded). Notice that , and We find that
где обозначает множество орбит перестановки .
where denotes the set of the orbits of permutation .