GRAFICAS PLANAS

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

¿Puede diseñarse un sistema de manera que las autopistas no se crucen, la figura anterior ilustra un sistema d las autopistas?

Una gráfica es plana si se puede dibujar en el plano sin que sus aristas se crucen. Al diseñar circuitos impresos es deseable tener el menor número de cruces posibles; así, el diseñador de circuitos impresos se enfrenta con el problema de graficas planas. Si una gráfica plana conexa se  dibuja en el plano, este se divide en regiones contiguas llamadas caras. Una cara se caracteriza por el ciclo que forma su frontera. Por ejemplo en la siguiente grafica la cara A tiene como límite el ciclo (5, 2, 3, 4,5) el límite de la cara C es el ciclo (1, 2, 5,1). La cara exterior se considera limitada por ciclo (1, 2, 3, 4, 6,1). La grafica de la figura es igual a 4 caras, e igual a 8 aristas y 6 vértices, obsérvese que F, E y V satisfacen la siguiente ecuación.