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 gráficas 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
gráfica 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 gráfica de la figura es igual a 4 caras, e igual a
8 aristas y 6 vértices, observe que F, E y V satisfacen la siguiente ecuación.
F=E-V+2
No hay comentarios.:
Publicar un comentario