"caras" de un grafo no plano

Question

Buenas tardes,

Tengo una pregunta acerca de los conceptos de la teoría de grafos. La teoría de grafos es un campo bastante extraño a mi conocimiento, por lo que mi pregunta es tal vez estúpido.

Para un plano gráfico, podemos definir sus caras como sigue : borramos todas sus aristas y los vértices del plano. A continuación, la parte restante del avión es una colección de piezas (componentes conectados). Cada pieza se llama una cara.

Así que cómo se definen los rostros de un no-plana del gráfico? Me gustaría saber si podemos definirla a partir de la intuitiva figura de un gráfico.

Gracias de antemano,

Duc Anh

EDIT : me gustaría explicar más donde mi pregunta viene. En esta diapositiva http://www.aimath.org/~hogben/Goins.pdf, el autor escribe $K_{3,3}$ $6$ vértices, $9$ bordes y $3$ caras, así que me pregunto cómo estas caras están definidos? O sólo podemos definir ellos después de incrustar el gráfico en un poco de la superficie de género $g$?

Answer 1

Tal vez esto es algo que usted quiere: cualquier gráfico $G$ puede ser embebido en una compacta superficie $S_g$ % género $g$, $g$. El mínimo de tal $g$ se llama el género de $G$. Entonces las caras de un grafo no plano pueden definirse como las regiones de la incrustación de $G$ $S_g$.

Answer 2

En general, la respuesta a tu pregunta es no---a partir de una representación abstracta $G=(V,E)$ de un gráfico, usted no puede obtener inmediatamente cualquier información acerca de sus caras en una incrustación en una superficie. No todo está perdido, sin embargo: es posible Que desee buscar en las rotaciones. En términos simples, si para cada vértice $v$ $G$ de definir un orden en el que todas las aristas adyacentes a $v$ se encontraría en una rotación alrededor de $v$, estas órdenes determinar una incrustación de $G$ en algunos orientable de la superficie: la selección de los diferentes órdenes de rotaciones le dará diferentes incrustaciones.

Answer 3

No hay ninguna definición razonable de las caras de un gráfico arbitrario. Incluso para un plano gráfico de la definición de las caras se supone que además de la (resumen) gráfico de hormigón con una incrustación en el avión es dado. Por ejemplo, tener una gráfica construida a partir de dos vértices $A,B$ por su vinculación con simples caminos de longitudes $1,3,2,3$ (introduciendo la necesaria $5$ vértices intermedios). Este gráfico es sin duda plana, pero no contienen una cara triangular? Eso depende de cómo los caminos están incrustados en el avión (el orden dado sugiere una incrustación que no da lugar a una cara triangular, pero sí existe una incrustación de este gráfico con una cara triangular. Para obtener más general de las gráficas, se puede acordar que cualquier ciclo en el grafo se define una cara de algunos de integración en una lo suficientemente complicado superficie.

Answer 4

Para un plano gráfico, podemos definir sus caras como sigue: borramos todas sus aristas y los vértices del plano. A continuación, la parte restante del avión es una colección de piezas (componentes conectados). Cada pieza se llama una cara.

Es similar a la plana.

Una cara de la incrustados graph es una arcwise componente conectado de la superficie, menos el de la gráfica.

Por ejemplo, el toro es arriba y abajo conectado, a la izquierda y a la derecha conectado.

Por lo $K_{3,3}$ tiene 3 caras en el toro.