Colorear un grafo con cuatro colores

figura1:

Coloración de grafos

Grafos

Un grafo aquel que se compone de un conjunto de puntos, llamados vértices, y de líneas queunen los puntos, llamadas aristas.En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada arista talque aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes.
Para la coloracion además de un grafo G, dispondremos de una paleta de colores, esto es, un conjuntoS = {a, b, . . . } a cuyos elementos nos referiremos como los colores. El uso de esta terminolog´ıatiene su explicaci´on, que veremos en un momentp.Una coloraci´on de G con los colores de S consistirá en asignar a cada vértice de G unelemento de S, es decir, un color, de manera que los extremos de cada arista reciban coloresdistintos. No se trata de una coloracion libre. Formalmente, una coloración de G con coloresde S es una aplicación.

El teorema de los cuatro coloresEn 1852 Francis Guthrie planteó el problema de los 4 colores, resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken.El teorema de cuatro colores establece que cualquier mapa geográfico puede ser coloreado con cuatro colores diferentes, de forma que no queden regiones adyacentes con el mismo color. Dos regiones se dicen adyacentes si comparten un segmento de borde en común, no solamente un punto.La forma precisa de cada país no importa; lo único relevante es saber qué país toca a qué otro. Estos datos están incluidos en el grafo donde los vértices son los países y las aristas conectan los que justamente son adyacentes. Entonces la cuestión equivale a atribuir a cada vértice un color distinto del de sus vecinos.

Algoritmo de coloración

Básicamente el algoritmo emplearía dos ciclos (enalgunos casos usa while, en otros casos ciclos for)de esta forma por cada vértice no coloreado visitasus adyacentes y comprueba si ya fueroncoloreados, si no han sido pintados, entonces loscolorea de tal forma que no hayan vérticesconsecutivos con la misma tonalidad de color.Este algoritmo en su forma básica nos lleva untiempo O(v²).

procedimiento del algoritmo

• Escoger inicialmente un color y un nodo arbitrario como punto de partida.

• Tratar de Asignarle ese color al mayor número posible de nodos,respetando que sus nodos adyacentes tengan distinto color.

• Escoger otro vértice aun no coloreado y un color distinto y repetir elproceso hasta haber coloreado todos los vértices.

Gracias a la teoría de Grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura.Los grafos se utilizan los mismos también para modelar trayectos como el de una línea de autobús a través de lascalles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.Para la administración de proyectos, utilizamos técnicas como PERT en las que se modelan los mismos utilizandografos y optimizando los tiempos para concretar.

En mi opinion los grafos son de gran utilidad aunque no lo parezca y hayan muchos que desconozcan sus usos, si bien es cierto a medida pasa el tiempola vida se va haciendo más compleja y se necesita de soluciones prácticas a tantos problemas que van surguiendo. En lo personal me llama mucho la atención,esta forma de usar la coloración de grafos por ejemplo en aplicaciones para la telefonía móvil.En este link hay un ejemplo de telefonía móvil que me gusto mucho y se los recomiendo. http://www.seccperu.org/files/colorGrafos.pdf

Bibliografía

http://www.seccperu.org/files/paper.pdf

http://es.wikipedia.org/wiki/Coloraci%C3%B3n_de_grafos1

http://www.youtube.com/watch?v=moZdSyN1KuI (video)