Grafo embebido

El grafo de Heawood i el mapa associat embebido en un bou

En teoria de grafos topològica, una incrustación d'un grafo $G$ en una superfície $\Sigma$ és una representació de $G$ sobre $\Sigma ,$ en la que les seues vèrtiços estan associats en punts de $\Sigma$ i els seus costats s'associen en arcs simples (imàgens homeomórficas de $[0,1]$) de $\Sigma$, de tal forma que:

• Els extrems de l'arc associat a un costat $e$ són els punts associats als vèrtiços extrems de $e$
• Cap arc inclou punts associats a atres vèrtiços
• Dos arcs mai es tallen en un punt interior a qualsevol dels arcs

Ací s'entén per superfície una varietat d'orde $2$ compacta i conexa.

De manera informal, una incrustación d'un gràfic en una superfície és un dibuix del gràfic en la superfície de tal manera que els seus costats es intersequen solament en els seus punts extrems. És ben sabut que qualsevol gràfic finito es pot incrustar en l'espai euclídeo tridimensional ${ℝ}^3$. Per definició, un grafo pla és aquell que es pot incrustar en un espai euclídeo bidimensional ${ℝ}^2.$

A sovint, un embebido es considera una classe d'equivalència (baix homeomorfismes de $\Sigma$) de les representacions del tipo que s'acaba de descriure.

Alguns autors definixen una versió més dèbil de la definició de "incrustación de grafos" en ometre la condició de no intersecció per als costats. En tals contexts, la definició més estricta es descriu com incrustación de grafos sense creus.

Este artícul tracta solament de la definició estricta de incrustación de grafos. La definició més dèbil es discutix en els artículs "dibuix de grafos" i "número de creuament".

Terminologia

Si un grafo $G$ està incrustat en una superfície tancada $\Sigma$, el complement de l'unió dels punts i arcs associats en els vèrtiços i arestes de $G$ és una família de regions (o cares). Una incrustación de 2 celes, incrustación celular o mapa és un embebido en el que cada cara és homeomorfa a un disc obert. Una incrustación tancada de 2 celes és un embebido en el que el tancament de cada cara és homeomorfo a un disc tancat.

El gènero (o també genus) d'un Grafo és l'número entero mínim $n$ tal que el gràfic es pot embeber en una superfície de genus $n$. En particular, un grafo pla té el gènero $0$ perque es pot dibuixar en una esfera sense autocruzarse. El gènero no orientable d'un grafo és l'número entero mínim $n$ tal que el grafo en qüestió es pot embeber en una superfície no orientable de gènero (no orientable) $n$.

El gènero de Euler d'un grafo és el mínim sancer $n$ tal que el grafo es pot embeber en una superfície orientable de gènero (orientable) $n/2$ o en una superfície no orientable de gènero (no orientable) $n$. Un grafo és orientablemente simple si el seu gènero de Euler és més chicotet que el seu gènero no orientable.

El gènero màxim d'un grafo és el màxim número entero $n$ tal que el gràfic pot ser una cela $2$ embebida en una superfície orientable de gènero $n$.

Embebido combinatori

Artícul principal → Sistema de rotació.

Un grafo embebido definix de forma única órdens cíclicos d'arestes incidents en el mateix vèrtiç. El conjunt de totes estes ordenacions cíclicas es diu sistema de rotació. Les incrustaciones en el mateix sistema de rotació es consideren equivalents i la classe de embebidos d'equivalència corresponent es denomina embebido combinatori (a diferència del terme embebido topològic, que es referix a la definició anterior en térmens de punts i curves). A voltes, el propi sistema de rotació es denomina embebido combinatori.

Un grafo incrustat també definix órdenaciones cíclicas naturals de costats que constituïxen els llímits de les cares de la incrustación. No obstant, el maneig d'estos órdens basats en cares és menys senzill, ya que en alguns casos algunes vores poden travessar-se dos voltes en un llímit de cara. Per eixemple, est és sempre el cas de embebidos d'arbres, que tenen una sola cara. Per a superar este inconvenient combinatori, es pot considerar que cada costat està dividit longitudinalmente en dos mijos costats o vores. Segons esta convenció, en tots els recorreguts de llímits de cares, cada mig costat es recorre solament una volta i els dos mijos costats del mateix costat sempre es recorren en direccions opostes.

Atres representacions equivalents de embebidos celulars inclouen als grafos de cinta, un espai topològic format en pegar junts discs topològics per als vèrtiços i els costats d'un gràfic embebido, i als mapes de grafos codificats, un grafo cúbic de color de vora en quatre vèrtiços per a cada vora del gràfic incrustat.

Vore també

• Encaix, per a un atre tipo de embebidos
• Embebido en llibre
• Gruixa (teoria de grafos)
• Llista d'arestes doblement conectades, una estructura de senyes per a representar un gràfic embebido en un pla
• Mapa regular (teoria de grafos)
• Teorema de Fáry, que afirma que sempre és possible obtindre un embebido en una llínea recta d'un grafo pla
• Triangulació