Coloreado de grafos

Dado un grafo, el problema consiste en asignar un color a cada vértice de un conjunto de M colores, de forma que no haya dos vértices adyacentes (es decir, unidos por una arista) del mismo color. Un ejemplo característico es el coloreado de mapas, en el cual cada vértice representa un pais y cada arista una frontera entre dos países.

Cuatro colores son suficientes para colorear cualquier mapa, sin embargo hay ocasiones en las que necesitaremos menos colores.

En el árbol de exploración del procedimiento de vuelta atrás cada nivel representa una asignación de color a un vértice, y cada nodo tendrá un hijo por cada color que se le puede asignar al vértice.

En la siguiente imagen se muestra un ejemplo de coloreado de grafos:

Puedes aprender este algoritmo en la zona de visualización. En primer lugar introduce el número de nodos del grafo y pulsa RESET. A continuación rellena la matriz de adyacencia del grafo, introduciendo un 1 si hay una arista entre los nodos y un 0 si no la hay. Por último pulsa ACTUALIZAR. Podrás observar la evolución del algoritmo y de las estructuras de datos implicadas mediante los botones de control de la parte superior.