Una gráfica dibujada en el plano es una representación de la gráfica.
Las Figuras 1 y 2 son dos representaciones distintas en el plano de K4. Aquélla tiene un cruce mientras ésta no.
El número de cruces de una representación es el número de pares diferentes de aristas que se intersecan; el número de cruce (G) de una gráfica G es el mínimo de los números de cruces de todas las representaciones de G en el plano. Así, una representación es plana si no tiene cruces. En otras palabras, una gráfica G es plana si (G) = 0. La Figura 2 muestra que K4 es plana.
Supón que G es plana. Si construimos una nueva gráfica insertando un nuevo vértice de grado dos “en medio” de una arista (división de una arista) o borrando un vértice de grado dos y uniendo sus dos vértices adyacentes (elidir un vértice), esa nueva gráfica también será plana. Gráficas que pueden ser obtenidas de otra por estas operaciones se llaman homeomorfas.
El Teorema de Euler
Si un grafo se puede dibujar de modo que no se corten sus lados (aristas) excepto en los vértices se dice que es un grafo plano.
El grafo de la figura es un grafo plano, porque aunque en la figura de la izquierda, las aristas se cortan en puntos distintos de los vértices, se puede encontrar un grafo isomorfo a él, el de la derecha, en el que las aristas no se cortan.
Cuando esté así dibujado, diremos que está representado apropiadamente.
Un grafo plano, apropiadamente representado divide al plano en distintas regiones, que llamaremos caras. Si se denota el número de caras por C, el número de vértices por V y el número de lados por A, en la figura se tiene que C = 4, V = 4 y A = 6.
En todo grafo conexo y plano que esté apropiadamente representado se verifica que el número de caras más el de vértices menos el de aristas vale 2.
Es decir C + V – A = 2 (cuando se cuenta la cara exterior)
Si no se cuenta la cara exterior: C+V – A = 1.
0 comentarios :
Publicar un comentario