Recordemos que en días pasados hablamos de grafos conexos e introducimos los grafos planos, mapas y la coloración de grafos.
La coloración de grafos es una forma de asignar etiquetas, llamadas colores, a elementos del grafo. En una coloración los vértices de un grafo cumplen que ningún vértice adyacente comparte el mismo color. Un caso particular es la coloración de las aristas: asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color. El proceso lo podemos repetir con las caras de un grafo plano, asignando un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes. En este caso se trata de un grafo plano.
Un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce. Un mapa es un grafo plano en el que nos interesan las caras entre las aristas.
Un de los resultado más interesante de los grafos planos es el Teorema de Euler:
Si un grafo simple plano conexo tiene $v$ vértices, $a$ aristas y $c$ caras, entonces $v − a + c = 2$
| Ejercicio: Estudiar si el grafo representado por la matriz [0,1,0,1,0,0; 1,0,1,0,0,0; 0,1,0,1,1,1; 1,0,1,0,1,1;0,0,1,1,0,0; 0,0,1,1,0,0] es plano. |