[ Foro de Pascal ]
Buenas noches profesor Nacho, es primera vez que me dirijo a usted y quisiera en primer lugar darle las gracias por crear espacios como este para el aprendizaje, nunca le había escrito pero si llevo algún tiempo siguiendo su curso de pascal del cual he aprendido muchísimo. En esta oportunidad se me presento un problema con el cual no he podido valerme con las herramientas que cuento y le pido su ayuda. El problema es el siguiente:
Necesito crear un programa que genere aleatoriamente una matriz de adyacencia que será la representación de un grafo, la misma es simétrica ya que es un grafo no dirigido, hasta allí todo bien, cree la matiz triangular superior luego realice la simetría y perfecto, el problema está en que me piden que realice el famoso problema del coloreo de grafos, tratando de obtener la menor cantidad de colores posibles. Quisiera que por favor me sugiriera una estructura de datos adecuada para tratar tal problema y una aproximación aunque sea al algoritmo para colorear el grafo. Me explico no es necesario colorearlo realmente lo que necesito es en base a la matriz que representa al grafo obtener la cantidad de colores empleados procurando que la misma sea lo más pequeña posible.
Muchísimas gracias de antemano por la atención prestada!!
Buenas tardes, si por casualidad existe alguna duda sobre el problema planteado o no lo he dejado claro por favor, escribanlo por acá. Gracias a todos los que se interesen!!!
Hola Armando.
La verdad es que esta semana he estado muy liado (aún lo estoy), pero he tenido el problema en la cabeza metido.
He estado la semana pasada trabajando con grafos y algoritmos (de Prim, de Ruta más corta,...) y este de los colores me llamó la atención.
Yo opino que la mejor estructura de datos es sin duda la matriz de adyacencia ya creada, más otra matriz que guarde colores. Esta última sería como la matriz de adyacencia de la de adyacencia.
Creo que el secreto está en el algoritmo, más que en el tipo de estructura, ahora bien: una matriz hace normalmente los algoritmos un poco más sencillos.
A mí se me ocurre ir recorriendo la matriz e ir comprobando los colores de los nodos. Si no hubiese color, asignaría uno distinto del resto de alrededor (que será un entero o byte en la casilla correspondiente, en la matriz de colores). También llevaría una variable "máximo", de forma que guardase el número del color más alto, es decir, el número de colores.
No sé si he servido de ayuda, pero intentaré crear un programa que resuelva esto (si puedo, para final de mes, por que antes tengo que hacer otros dos).
Gracias por proponer un programa tan interesante.
Adiós.
Bueno muchas gracias por interesarte en el problema, es en verdad un reto para mi solucionarlo pero tengo en contra que no llevo mucho tiempo programando y desconozco quizas herramientas que me puedan ayudar. he avanzado un poco desde que formule la duda, estoy trabajandolo con listas enlazadas ya que los elementos de la matriz de adyacencia se generan aleatoriamente cada vez que se ejecuta el programa la cantidad de "colores" varia, ademas que lo estoy tratando de hacer un poco mas completo y es que luego de colorear el grafo muestre todas las listas de elementos compatibles ademas de por supuesto el fin del programa que es el numero de listas (colores empleados).
Las estructuras que estoy usando son:
- array bidimensional: La Matriz de adyacencia (obviamente cuadrada).
- un array unidimencional del tamaño de elementos con el que este trabajando que tiene una particularidad, cada celda es el inicio de una lista enlazada en donde con el algoritmo de coloreo se iran agregando los elementos compatibles.
- una lista enlazada que almacena numeros enteros: Numero de elementos a colorear. (Lista de elementos no coloreados).
Todo esto tiene el siguiente fin: Se llenan aleatoriamente cada una de las celdas de la matriz con unos o ceros, con una funcion (que es la que me falta diseñar) se van comparando los elementos de la lista de elementos a colorear y los que sean compatibles se agregan al vector de listas en la posicion que les corresponda.
Lo siento, he tenido una racha de no poder mirar el foro. Supongo que con coloreado de grafos te refieres a colorear los vértices, de modo que dos vértices adyacentes no compartan el mismo color:
http://es.wikipedia.org/wiki/Coloraci%C3%B3n_de_grafos
Se puede hacer de varias formas, pero por ejemplo podrías tomar dos alternativas radicalmente distintas, ambas basadas en un conjunto matriz de adyacencia + lista de colores utilizables para un nodo:
- Una basada en backtracking, que genere un nuevo grafo a partir de cada situación actual, en la que se fije el color para un nuevo nodo, y luego otro a partir de ese, de forma recursiva. Esto tendría un coste computacional elevado, tanto en espacio como en tiempo, pero garantizaría que la solución, si existe, se encontrará.
- Un algoritmo voraz, que tome una decisión y la aplique hasta el final, con todas sus consecuencias, con el riesgo de que si en algún momento se da un paso que no sea el óptimo, quizá no se encuentre la solución óptima, o ni siquiera se encuentre solución, pero a cambio, la solución se busque de forma mucho más rápida.
En ambos casos necesitarás una función auxiliar que te diga si un cierto color es (todavía) aceptable para un nodo, recorriendo los adyacentes y comprobando los colores que tienen éstos.
En cuanto a las estructuras a usar: estoy de acuerdo en la matriz de adyacencia, y en una lista de colores para cada nodos (ya es decisión de diseño qué guardas en ella: los colores ya escogidos, o los colores que todavía puedes usar... para eso también influye el tipo de algoritmo que emplees). Puedes usar una lista de nodos que no has coloreado, o puedes simplemente colorear en orden, del nodo 1 al nodo n, según la forma en que propagues información de un nodo a otro. Eso sí... el resultado depende del orden en que recorras los nodos, así que hay algoritmos que te permiten ordenar los nodos antes de comenzar.
Si no lo haces por practicar, sino que tienes que buscar una soluciónn eficiente, tienes mucha información interesante en Internet, especialmente apuntes de primer o segundo año de Ingeniería en Informática, como estos:
http://www.uam.es/personal_pdi/ciencias/gallardo/capi10-grafos-coloraciones-0910.pdf
(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)