Graficas Planas

3 ciudades C1,C2,C3 deberían conectarse en forma directa mediante autopistas con cada una de otras 3 ciudades C4,C5,C6.

 Puede diseñarse un sistema de carretera de manera que las autopistas no se crucen, la fig. anterior ilustra un sistema donde las aristas se cruzan.

Una gráfica plana se puede dibujar en el plano sin que sus aristas se crucen. Al diseñar circuitos impresos es decible tener el menor de cruces posibles, así el diseñador de circuitos impresos se enfrentan con el problema de gráficas planas.

Si una gráfica plana conexo se dibuja en el plano , esto se divide en regiones continuas llamadas caras. Una cara se caracteriza por el ciclo que forma su frontera. Ejemplo en la siguiente gráfica la cara A tiene como limite el ciclo (5,2,3,4,5) . B tiene el  ciclo (1,2,5,1), la cara anterior D se considera limitada por el ciclo (1,2, 3,4,6,1). La gráfica de la figura tiene 4 caras  e igual  8 aristas y 6 vértices.

F= 4 varas

E= 8 aristas

V= 6 vértices

F= E –V +2

F= 8-6+2

F = 2