Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Комбинаторлық математикада айналу жүйелері (оларды комбинаторлық ендірулер немесе комбинаторлық карталар деп те атайды) графтардың бағытталған беттерге ендірілуін кодтайды, әр төбесінің айналасындағы граф қабырғаларының шеңберлік ретін сипаттау арқылы. Айналу жүйесінің формалды анықтамасы пермутациялар жұбын қамтиды; мұндай жұп мультиграфты, бетті және мультиграфтың бетке 2 ұяшықты ендірілуін анықтау үшін жеткілікті. Кез келген айналу схемасы жабық бағытталған бетте (бағдарлауды сақтайтын топологиялық теңдестікке дейін) байланысты мультиграфтың бірегей 2 ұяшықты ендірілуін анықтайды. Керісінше, бағытталған жабық беттегі байланысты G мультиграфының кез келген ендірілуі G-ді негізгі мультиграф ретінде пайдаланатын бірегей айналу жүйесін анықтайды. Айналу жүйелері мен 2 ұяшықты ендірулер арасындағы осы маңызды теңдестік алғаш рет 1890 жылдары Лотар Хефтер екі жақты түрінде шешті және 1950 жылдары Рингель кеңінен пайдаланды. Эдмондс тәуелсіз түрде теореманың бастапқы түрін берді және оның зерттеуінің егжей-тегжейлерін Юнгс танымал етті. Гросс пен Альперт мультиграфтарға жасалған жалпылауды ұсынды. Айналу жүйелері Рейнгольд және басқалар қолданған айналу карталарымен байланысты, бірақ олардан өзгеше. (2002) графтардың зигзаг көбейтіндісін анықтау үшін. Айналу жүйесі әр төбесінің айналасындағы қабырғалардың дөңгелек ретін көрсетеді, ал айналу картасы әр төбедегі қабырғалардың (дөңгелек емес) пермутациясын көрсетеді. Сонымен қатар, айналу жүйелерін кез келген граф үшін анықтауға болады, ал Рейнгольд және басқалар анықтаған айналу карталары тұрақты графтармен шектеледі.
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-де транзитивті әрекет етеді. Бағытталған бетте орналасқан G мультиграфының 2-ұяшықты кіріктіруінен айналу жүйесін алу үшін, 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-ге изоморфты болады.
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 .