Graficas Planas
* Una gráfica es plana si se puede dibujar en el plano sin que sus aristas se crucen.
Ejemplo:
Determine si la gráfica es plana. Si lo es,dibújela de nuevo sin que se crucen las aristas.
Luego de analizar detenidamente la gráfica observamos que si la podemos trazar sin que se crucen lasaristas, quedando asi:
Ahora vamos a aplicar la fórmula para hacer la verificación correspondiente.
Gráfica plana conexa con f = 7 caras (A, B, C, D, E), e = 10aristas y v = 5 vértices; f = e – v + 2
Entonces:
f = e – v + 2
7 = 10 – 5 + 2
7 = 7 Por lo tanto la gráfica es plana.
Además, es necesario conocer comodemostrar que ciertas gráficas no son planas:
* Se dice que una gráfica es plana si se puede dibujar en el plano sin que sus aristas se crucen, si y solo si Nocontiene una subgráfica homeomorfa a K5 o K3, 3 (teorema de Kuratwski).
* Dos graficas G1 y G2 son homeomorfas si G1 y G2 se pueden reducir a graficas isomorfasrealizando varias reducciones en serie.
* Existe isomorfismo de graficas cuando las figuras G1 y G2 definen las mismas graficas aunque parezcan diferentes.Entonces se puede decir que para que exista isomorfismo se debe tener el mismo número de vértices, de aristas, además, de que el grado de 2, luego de realizaruna reducción de serie.
* La reducción en serie se da cuando en una gráfica G las aristas (v, v1) y (v, v2) están en serie, y al hacer reducción en seriedesaparece v y solo queda v1, v2.
Apóyese del ejemplo planteado en la página 361 del texto base, para su mejor comprensión, utilizando el teorema de Kuratowski.
Regístrate para leer el documento completo.