Colorear Grafos con Algoritmos

¿Qué es un grafo?
Es aquel que se compone de un conjunto de puntos, llamados vértices, y de líneas que
unen los puntos, llamadas aristas. La Coloración de un grafo Consiste en la asignación de un color a cada vértice de
éste, de tal forma que no haya dos vértices del mismo color unidos por un arista
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.

La vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformados a una versión con vértices. Por ejemplo, una arista coloración de un grafo es justamente una vértice coloración del grafo de línea respectivo, y una coloración de caras de un grafo plano es una vértice coloración del grafo dual.

La convención de usar colores se origina de la coloración de países de un mapa, donde cada cara es literalmente coloreada. Esto fue generalizado a la coloración de caras de grafos inmersos en el plano. En representaciones matemáticas y computacionales es típicamente usado enteros no-negativos como colores. En general se puede usar un conjunto finito como conjunto de colores. La naturaleza del problema de coloración depende del número de colores pero no sobre cuales son.

¿Cómo colorear un grafo?


Se selecciona un vértice no coloreado y se le
asigna el nuevo color.
Se examina la lista de vértices no coloreados coloreados.
Para cada uno de ellos se determina si existe
alguna arista que una con un vértice que ya
tenga asignado el nuevo color color, si tal arista no
existe, se asigna el nuevo color al vértice.


Básicamente el algoritmo emplearía dos ciclos (en
algunos casos usa while, en otros casos ciclos for)
de esta forma por cada vértice no coloreado visita
sus adyacentes y comprueba si ya fueron
coloreados, si no han sido pintados, entonces los
colorea de tal forma que no hayan vértices
consecutivos con la misma tonalidad de color.
Este algoritmo en su forma básica nos lleva un
tiempo O(v²).

Uno de los mayores aplicaciones de la coloración de grafos, es la asignación de registros en compiladores introducida en 1981.
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. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.

Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles 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 utilizando grafos y optimizando los tiempos para concretar los mismos.

Creo que para problemas con algoritmos de este tipo es de suma importancia poder reconocer que nos intereza mas si rapidez o eficiencia. puesto que al ser un algoritmo tan complejo debemos tener cuidado con la misma complejidad con el que sea estructurado, para poder reducir lo mas posible la cantidad de colores a usar, tiempo de ejecucion o eficiencia de codigo.

Por ultimo dejo este excelente video con el que queda mejor plasmado la idea de coloracion de un grafo.







Bibliografía
http://www.youtube.com/watch?v=moZdSyN1KuI
http://www.sol.com/algoritmos/pagina02.asp
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos
http://www.infovis.net/printMag.php?num=137&lang=1
http://www.monografias.com/trabajos/grafos/grafos.shtml