Coloreado de grafos

De Wikipedia, la enciclopedia libre

Este artículo debería estar en Wikilibros ya que es una guía o manual en vez de un verdadero artículo enciclopédico.
Si modificas este artículo dándole una orientación enciclopédica, elimina por favor esta plantilla.

[editar] Descripción detallada del problema

Dados un grafo G y un número m > 0, queremos descubrir todas las formas de pintar los vértices de G utilizando un máximo de m colores, de tal forma que ningún par de vértices adyacentes tengan el mismo color.

[editar] Estrategia de resolución

Si numeramos los colores de 1 a m y el grafo tiene n vértices numerados de 1 a n, una posible solución al problema puede representarse como una tupla (x1, ..., xn), donde xi ∈ {1, ..., m} es el color con el que se ha pintado el vértice i. Las soluciones tienen que cumplir que solo utilizan colores válidos y que dos vértices adyacentes no tienen el mismo color.

[editar] Árbol de exploración

Necesitamos un árbol de exploración, pues el conjunto de soluciones posibles es demasiado grande y necesitamos estructurar el espacio a explorar, tratando de descartar en bloque posibles soluciones no satisfactorias. Nuestro árbol de exploración tendrá:

• m hijos por nodo.
• n niveles.

En cada nivel se toma la decisión de la etapa correspondiente. Cada nodo del árbol de exploración corresponde a una tupla parcial o a una tupla completa, satisfaciendo las restricciones explícitas. Los nodos solución son los correspondientes a las tuplas completas que satisfacen las restricciones implícitas.

En cada etapa comprobaremos que el color asignado al vértice k no ha sido asignado a ningún vértice adyacente a k previamente coloreado. Utilizar en este caso el mecanismo de marcaje no sería sencillo. Tendríamos que mantener, para cada vértice i y color j, la información de si hay algún vértice adyacente a i pintado de color j. Guardando dicha información en una matriz usado[i, j], comprobar si podemos pintar de color j el vértice i tendría un coste constante. Sin embargo, marcar sería costoso ya que tendríamos que recorrer los vértices k adyacentes a i para marcar usado[i, j]. La tarea de desmarcar resultaría mucho más complicada. Por esto no utilizaremos marcadores en este caso.

Existen diversas representaciones para el grafo. Utilizaremos la que usa una matriz de adyacencia indicando si cada par de vértices son adyacentes. Tenemos así un coste constante en la operación está-arista?.

[editar] Implementación en Pseudocódigo

[editar] Funciones Auxiliares

Para comprobar si podemos pintar de color j el vértice i, usaremos la función test-color, que comprueba si sigue sin haber dos vértices adyacentes ya coloreados con el mismo color. Como al nivel k se llega después de comprobar la factibilidad en el nivel k – 1, sabemos que la tupla (x1, ..., xk – 1) es factible (no hay vértices adyacentes con el mismo color), por lo que basta comprobar que la propiedad se mantiene con respecto al nuevo vértice xk.

 fun test-color(G: grafo[n], sol[1..n] de 1..m, k:1..n) dev respuesta: bool
   respuesta := cierto;
   j := 1;
   mientras j < k  respuesta hacer
     si está-arista?(j, k, G)  está-arista?(k, j, G) entonces
       respuesta := sol[j] ≠ sol[k];
     fsi
     j := j + 1;
   fmientras
 ffun

[editar] Algoritmo principal

Teniendo la función test-color, el algoritmo de coloreado es el siguiente:

 proc coloreado-grafo(e G:grafo[n], e m:nat+, sol[1..n] de 1..m, e k:1..n)
   para color = 1 hasta m hacer
     sol[k] := color
     si test-color (G, sol, k) entonces
       si k = n entonces imprimir(sol);
       si no coloreado-grafo(G, m, sol, k + 1);
       fsi
     fsi
   fpara
 fproc

[editar] Llamada inicial

La llamada inicial para resolver el problema es coloreado-grafo(G, m, sol, 1). Este algoritmo es válido tanto para grafos dirigidos como para grafos no dirigidos.

[editar] Referencias

• Martí Oliet, N,; Ortega Mallén, Y.; Verdejo López, J.A.; ESTRUCTURAS DE DATOS Y MÉTODOS ALGORÍTMICOS. Ejercicios resueltos. Pearson Education 2004