Estructura de Datos

El problema de coloración de grafos, es considerado uno de los más interesantes en lo que respecta a la teoría de grafos. Este problema consiste en usar la menor cantidad posible de colores para poder colorear un grafo, de tal forma que los nodos adyacentes nunca tengan el mismo color, se intenta con todos los colores uno a la vez sucesivamente asta encontrar la coloración que sea valida.


Es un problema de tipo NP-completo.
Este algoritmo en su forma básica nos lleva un tiempo O(v²).
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 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 Dijkstra.
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.
Los grafos como una nueva manera de organizar la información en una base de datos.


Comentario.
Por medio de los grafos se ha logrado dar solución a problemas cotidianos de nuestras vidas, sin que nos percatemos de esto, gracias a ellos contamos con medios de transporte, comunicación, programación de actividades. Ayudando a organizarnos.

Link de Interes.
http://www.dma.fi.upm.es/gregorio/grafos/paginagrafos.html

Bibliografía.
Joomla.Coloracion Grafos.23 abril 2010
http://www.algovidea.cl/index.php?option=com_content&view=article&id=49&Itemid=62
Pedro Bello López.Primavera 2007.Grafos.23 abril 2010
http://www.cs.buap.mx/~pbello/grafos.pdf