Sistema de rotació

En matemàtiques combinatòrias, un sistema de rotació (també cridat incrustación o embebido combinatori) servix per a codificar grafos embebidos en superfícies orientables, descrivint l'ordenació circular de les vores d'un grafo al voltant de cada vèrtiç.

Una definició més formal d'un sistema de rotació implica parells de permutació. Dits parells són suficients per a determinar un multigrafo, una superfície i un embebido de dos celes del multigrafo sobre la superfície.

Cada esquema de rotació definix una incrustación única de dos celes d'un multigrafo conectat en una superfície orientada tancada (fins a l'equivalència topològica que conserva l'orientació). Pel contrari, qualsevol incrustación d'un multigrafo conectat G en una superfície tancada orientada definix un sistema de rotació únic que té G com la seua multigrafo subjacent. Esta equivalència fonamental entre els sistemes de rotació i els embebidos de dos celes va ser establida per primera volta de forma dual per Lothar Heffter en la década de 1890 i utilisada àmpliament per Ringel durant la década de 1950. Independentment, Edmonds va donar la forma original de la teorema i els detalls del seu estudi han segut popularisats per Youngs. La generalisació a multigrafos va ser presentada per Gross i Alpert.

Els sistemes de rotació estan relacionats, pero no són els mateixos, en els mapes de rotació utilisats per Reingold et al. (2002) per a definir el producte en zig-zag de grafos. Un sistema de rotació especifica una ordenació circular de les vores al voltant de cada vèrtiç, mentres que un mapa de rotació especifica una permutació (no circular) de les vores en cada vèrtiç. Ademés, els sistemes de rotació es poden definir per a qualsevol grafo, mentres que els mapes de rotació definits segons Reingold et al. estan restringits a grafos regulars.

Definició formal

Formalment, un sistema de rotació es definix com un parell (σ, θ) a on σ i θ són permutació que actuen sobre el mateix conjunt base B, θ és un punt fix lliure d'involució, i el grup <σ,  θ> generat per les accions σ i θ transitivamente en B.

Per a deduir un sistema de rotació d'un embebido de 2 celes d'un multigrafo conectat G en una superfície orientada, B deu consistir en els darts (o banderes, o semiaristas) de G; és dir, per a cada aresta de G es deuen formar dos elements de B, un per a cada extrem de l'aresta. Inclús quan una aresta té el mateix vèrtiç que els seus dos extrems, es creen dos darts per a eixa aresta. Siga θ(b) l'atre dart format per la mateixa aresta que b; açò és clarament una involució sense punts fixos. Ara siga σ(b) el dart en la posició de les agulles del rellonge des de b en l'orde cíclico de les arestes que incidixen en el mateix vèrtiç, a on «les agulles del rellonge» es definixen per l'orientació de la superfície.

Si un multigrafo està incrustat en una superfície orientable pero no orientada, generalment correspon a dos sistemes de rotació, un per a cada una de les dos orientacions de la superfície. Estos dos sistemes de rotació tenen la mateixa involució θ, pero la permutació σ per a un sistema de rotació és l'inversa de la permutació corresponent per a l'atre sistema de rotació.

Recuperació del embebido del sistema de rotació

Per a recuperar un multigrafo d'un sistema de rotació, es dispon d'un vèrtiç per a cada òrbita de σ i una aresta per a cada òrbita de θ. Un vèrtiç és incident en una aresta si estes dos òrbites tenen una intersecció no buida. Aixina, el número d'incidències per vèrtiç és el tamany de l'òrbita, i el número d'incidències per aresta és exactament dos. Si un sistema de rotació es deriva d'un embebido de dos celes d'un multigrafo conectat G, el gràfic derivat del sistema de rotació és isomòrfic a G.

Per a embeber el gràfic derivat d'un sistema de rotació en una superfície, es deu formar un disc per a cada òrbita de σθ i pegar dos discs en una vora i sempre que els dos darts corresponents a i pertanyguen a les dos òrbites corresponents a estos discs. El resultat és un embebido de dos celes del multigrafo derivat, que les seues dos celes són els discs corresponents a les òrbites de σθ. La superfície d'este embebido es pot orientar de tal manera que l'orde en el sentit de les agulles del rellonge de les vores al voltant de cada vèrtiç siga el mateix que l'orde en el sentit de les agulles del rellonge donat per σ.

Vore també

• Aplicació combinatòria

Bibliografia

• (2004) Graphs on Surfaces and Their Applications (vol. 141), Berlin, New York: Springer Science+Business Mija. ISBN 978-3-540-00203-1..