CAPÍTULO 3. RELACIONES
92
Quisiéramos hacer la instalación de tal forma que las líneas de luz y teléfono y las tuberías
de agua no se crucen. ¿Es posible hacerlo? Para responder esta pregunta necesitaremos
introducir otros conceptos sobre grafos.
En general en un grafo los lados pueden cruzarse. Los grafos que se pueden representar
en un plano sin que se crucen su lados se llaman grafos planos o planares.
Por ejemplo, el grafo de la izquierda es planar, pues también lo podemos representar
como en el diagrama de la derecha.
4
4
#
$
1
$
#
3
$
#
1
3
#
$
2
2
Podemos entonces enunciar el problema del Agua, Luz y Teléfono de manera equivalente
preguntando si su grafo es planar. Si lo es, entonces la respuesta a la pregunta inicial es “si”
y si no es planar entonces la respuesta es “no”.
Cuando se representa en un plano un grafo conexo y plano, queda dividido en regiones
contigüas llamadas caras. Por ejemplo, considere el siguiente grafo:
1
%
2
C
%
%
4
5
A
%
B
%
6
%
D
3
Hemos indicado sus 4 caras: A, B, C y D. Observe que D es la cara “exterior” del grafo.
Euler notó que no importa como tracemos el grafo en un plano, el número de caras es el
mismo. El número de caras (f ) está determinado por el número de vértices (v) y el número
de lados (e) mediante la fórmula siguiente
Fórmula de Euler para Grafos: Si G es un grafo plano, conexo, con e lados, v vértices y
f caras, entonces
f = e − v + 2.