Coloración de Grafos Planos a través de SAT

1. DESCRIPCIÓN DEL PROYECTO

 El proyecto tiene como finalidad mostrar que el problema de coloración de grafos (NP-completo)  puede ser planteado como un problema SAT y resuelto con un método completo. El proyecto se enfoca a colorear grafos planos (o planar) (ver apéndice A) apoyándonos en el teorema de los cuatro colores (Francis Guthrie, 1890), el cual especifica que no se necesitan más de cuatro colores para lograr la coloración correcta de un grafo plano.

 Presentamos el proceso de reducción de un grafo a la forma normal conjuntiva así como la interpretación de la solución SAT al dominio de grafos.

 El resultado del sistema muestra el número cromático del grafo así como su coloración correspondiente.
 

2. ALTERNATIVAS DE SOLUCION SELECCIONADAS.

 2.1 Tabu Search y Simulated Annealing

En los trabajos [1] y [2] se reportan resultados al aplicar Tabu Search y Simulated Annealing en la coloración de vértices. Ambas técnicas se basan en el método del gradiente o descenso más pronunciado, esto es, se parte de una solución arbitraria x0 y en cada paso se efectúa un desplazamiento desde la solución actual xk a u na nueva solución xk+1 que se elige en la vecindad de xk de modo que el valor de la función objetivo no empeore. Las soluciones vecinas de xk son aquellas que se pueden obtener a partir d e xk con un sólo desplazamiento. La principal debilidad del método del gradiente es su incapacidad de escapar de los puntos que son mínimos locales. En cambio, tanto Tabu Search como Simulated Annealing consiguen alejarse de mínimos locales, para lo cual permiten empeorar la función objetivo temporalmente.

En Tabu Search si xk+1 pertenece a la vecindad de xk y xk pertenece a la vecindad de xk+1, entonces el método puede entrar en un ciclo si en el paso siguiente xk es la mejor solución. Para evitar ciclos se almacenan los últimos pares de soluciones en la llamada lista tabú. Si el par (x, y) está en la lista entonces el movimiento y ® x está prohibido.

Simulated Annealing no busca la mejor solución en la vecindad de xk sino que la escoge al azar y se acepta como la nueva solución con una cierta probabilidad. Inicialmente casi todos los movimientos desde una solución son aceptados. A medida que avanza el procedimiento, disminuye la probabilidad de aceptar movimientos que no mejoren la función objetivo. Esto se consigue controlando el parámetro que representa la temperatura.

La desventaja principal que se muestra en los resultados de coloración de grafos usando Tabu Search[1] y Simulated Annealing [2] es que no siempre arrojan el número cromático correcto (obtienen un número mayor) , aunque sí colorean el grafo en forma válida.
 

 2.2 Algoritmos de coloración secuencial.

Los algoritmos de coloración secuencial, también conocidos como coloración glotona (greedy coloring) van seleccionando un vértice de acuerdo a algún criterio específico, formando así un “orden” de coloración. Luego, en cada vértice lo van coloreando con un color que no tienen sus vecinos.

El orden en que se seleccionan los vértices afectan a la coloración [3], así que un buen orden de vértices puede traducirse en una buena coloración. No hay ninguna forma de obtener la solución óptima, sino que, se aplica el algoritmo de coloración secuencial varias veces hasta obtener la coloración válida.

 Los algoritmos de coloración secuencial proponen las siguientes variantes:

a) Primero el más grande. (LF) En este método, los vértices son ordenados en orden descendente de acuerdo a su grado. La idea aquí  es que los vértices de mayor grado serán más difíciles de colorear al último, y por eso se colorean primero.

b) Al último el más pequeño. (SL) Al igual que LF, este método selecciona el vértice con el grado más pequeño y lo coloca al final del ordenamiento. La diferencia principal con LF es que este vértice es luego borrado del grafo, reduciendo así el grado de sus vértices vecinos.

c) Saturación (SAT). A diferencia de LF y SL donde el orden de los vértices se determina de antemano, aquí los vértices son seleccionados durante el proceso de coloración. En saturación, el vértice con el grado de saturación más alta se selecciona para ser el próximo a colorear. El grado de saturación de un vértice es el número de colores diferentes usados pos sus vecinos. La idea es seleccionar el vértice que está más restringido.

 Los métodos anteriores determinan el número cromático así como la coloración del grafo. Tienen la ventaja de que su implementación es relativamente sencilla. La desventaja principal es el tiempo en obtener el resultado, así como seleccionar la mejor forma de ordenar los vértices a colorear. En caso de no seleccionar el orden correcto, el número de colores seguirá creciendo indefinidamente.
 

 2.3 Reducción del grafo a cláusulas FNC y su solución con un método
       completo.

  Este método reduce un grafo a cláusulas en la Forma Normal Conjuntiva. En este estado, podemos aplicar un método completo para resolver el problema SAT. Una vez asignados los valores de verdad que satisfacen a la fórmula, solo resta “interpretar” los valores de las variables al contexto de grafos. De aquí obtenemos el número cromático así como la coloración del grafo.

 Hemos enfocado el proceso anterior para aplicarse en grafos planos (véase Apéndice A), donde el número cromático puede ser como máximo 4 (Teorema de los 4 colores).

 La ventaja principal de este método de solución es que encontraremos el número cromático correcto así como la coloración correspondiente del grafo, y mostraremos que el tiempo de solución es menor que los algoritmos secuenciales.

 La desventaja que vemos es que para que sea eficiente solo trabajamos para grafos planos.
 

3. RELEVANCIA DEL PROYECTO

Se ha visto que existen varios métodos que resuelven el problema de coloración de grafos, pero hay pocos planteamientos para solucionarlo como un problema de satisfactibilidad.

 Esto se debe a que la forma de llevar un problema de coloración de grafos a SAT requiere de varios pasos, comenzando por el mapeo de problema de coloración de grafos a SAT, el problema del numero cromático a usar, así como ajustar un método completo de solución SAT a nuestra FNC, y obtener finalmente la solución en el contexto de grafos.

Desde nuestro punto de vista la relevancia de este trabajo está basada en que es posible encontrar el número cromático correcto (a diferencia de Tabu y Simulated Annealing) y la coloración del grafo al solucionar el problema SAT, sin depender de un orden (como algoritmos secuenciales) de los vértices.
 
 

4.ESTRATEGIAS DE SOLUCION

 El proceso que se describe a continuación ilustra la forma en que proponemos la solución para hallar el número cromático y la coloración del grafo plano:

a) Dado un grafo plano G, reducirlo a la forma normal conjuntiva (FNC).
b) Aplicar el método Davis & Putnam a la fórmula anterior.
c) Obtener los valores de verdad que satisfacen a la fórmula para 2,3 o 4 colores.
d) Traducir el resultado al contexto de grafos, obteniendo el número cromático y la coloración de cada vértice.

REFERENCIAS

[1] Chams, M., A. Hertz & D. de Werra, "Some experiments with simulated annealing for coloring graphs", Eur. J. Op. Res. 32, pp. 260-266, 1987
[2] Hertz, A. & D. de Werra, "Using Tabu Search Techniques for Graph Coloring", Computing 29, pp. 345-351, 1987.
[3] http://www.cs.uwa.edu.au/~chiy/gcolour.html
 
 
 

APENDICE A

Un grafo plano es un grafo que puede ser dibujado sobre una superficie plana de forma que sus aristas se intersectan únicamente en los vértices.