Grafos planos, formula de Euler y Teorema de Kuratowski.

Un grafo o multigrafo que se puede dibujar en el plano sin que se crucen sus arcos se llama plano. Aunque el grafo completo de K4 se suele dibujar con arcos que se cruzan como en la figura 6.1(a), también se puede dibujar sin que se crucen sus arcos como en la figura 6.1(b). Luego K4 es un grafo plano.

Formula de Euler: Euler dio una formula que relacionaba el numero de V de vértices, el numero E de arcos y el numero R de regiones de un mapa conexo. V-E+R=2. Es muy importante que el grafo correspondiente al mapa sea conexo, pues en caso contrario la formula no es cierta. En la siguiente figura tenemos  V=6, E=9 y R=5 y como afirma la formula de euler: V-E+R=6-9+5=2.

Teorema de Kuratowski:Un grafo es no plano si y solo si contiene un subgrafo homeomorfo a K3,3 o K5.

 

Intituto Tecnologico de Apizaco.

Autor: Elizabeth Sola Lira