GRÁFICAS PLANAS

GRÁFICAS PLANAS

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 dircuitos impresos se enfrenta con el problema de gráficas planas.

Si una gráfica plana convexa 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 (cinco, dos, tres, cuatro, cinco) y el límite de la cara C es el ciclo (uno, dos, cinco, uno). La cara exterior D se considerada limitada por el ciclo (uno, dos, tres, cuatro, seis, uno). La gráfica de la figura tiene f=4 caras, e=8 aristas y v=6 vértices. Obsérvece que f,e y v satisfacen la ecuación f=e-v+2.

En 1972, Euler probó que la ecuación se cumple para cualquier gráfica conexa plana.

f=e-v+2

f=8-6+2

4=2+2

4=4