Coloración de Grafos a través de
Por José María Vega Ramos , Enrique Ayala
Franco,Huberto Ayanegui Santiago
Abstract
Este trabajo resuelve el problema de coloración de grafos usando el algoritmo de Simulated Anneling y Davis & Putnam para cualquier grafo. En el trabajo anterior vimos como usar Davis & Putnam para colorear grafos planos. Ahora mostraremos cómo colorear cualquier grafo. La idea principal es utilizar Simulated Annealing para encontrar la aproximación del número cromático y posteriormente utilizar el método de Davis & Putnam a través de particiones binarias hasta encontrar el número cromático correcto.
Introducción
Anteriormente se realizó una investigación, en la cual se lograba colorear un grafo plano, llevándolo primero a su forma matricial (matriz de adyacencia), luego a su FNC, y finalmente con el algoritmo Davis&Putman se encontraba la coloración del grafo plano. En este caso se sabe que cualquier grafo plano puede ser coloreado con 4 colores ( Teorema de los cuatro colores). Ahora, buscamos colorear cualquier grafo, donde el número cromático puede ser cualquier entero positivo.
Existen algunos trabajos ya realizados en este contexto como el de Andreas Nolte y
Rainer Scharader [1], en donde ellos plantean una aplicación del algoritmo Simulated
Anneling para Colorear un grafo usando 3 colores, y el de M. Chams, A. Hertz, and D. De
Werra. [2] , en el cual ellos proponen la forma de colorear un grafo usando
Simulated Anneling en base a varios experimentos para colorear grafos. A decir verdad
nuestro problema principal es encontrar el numero cromático mínimo, dado cualquier
grafo, plano o no plano.
Conceptos relacionados con este trabajo:
Coloración de Grafos
El problema de Coloración de Grafos consiste en la asignación de colores a un
conjunto de n vértices, dado un grafo no dirigido con la única condición que para todo
par de vértices adyacentes estos no sean coloreados del mismo color .
Definición Formal de un Grafo coloreado
Considere un grafo G=(V,E) con el conjunto de vértices V y conjunto de aristas E. Una
coloración-K de G es una partición de V en subconjuntos K, V1,....,Vk tal que no hay dos
vértices en el mismo conjunto que son adyacentes. Es decir, si v,w pertenecen a Vi,
1<=i<=k entonces v,w no pertenecen a E. Los conjuntos V1,...,Vk se refieren como a
clases de colores o colores. El número cromático X(G) es definido como el k mínimo para
el cual G es coloreable. El problema de coloración puede definirse así: Dado un grafo G,
encuentre X(G) y la coloración correspondiente. La coloración de grafos es conocida como
un problema NP-completo [Garey-Johnson 1979, Littman, 1997].
Algoritmo Simulated Anneling
Simulated Anneling es un técnica de optimización para resolver problemas de
optimización combinacional. Asumimos un función de costo C(x) que nosotros
queremos minimizar en un espacio W. Si el problema es impracticable desde un punto de
vista computacional, nosotros forzaremos a usar algoritmos de aproximación. Estos
algoritmos presuponen la definición de configuración y un mecanismo de generación. Una
configuración es usualmente un elemento de W con alguna información adicional. Un
mecanismos de generación es un procedimiento para ir de una configuración a otra por una
pequeña perturbación (cambio). El conjunto de configuraciones que pueden ser alcanzadas
desde una configuración x en una transición es llamada la vecindad de x : N(x). Los
algoritmos Hill climbing comienzan en una configuración arbitraria y en cada paso de
cambian a la configuración vecindad con el costo mínimo. Estos algoritmos son muy
rápidos, pero en la mayoría de los casos estos alcanzan un mínimo local, en lugar de un
mínimo global. Los algoritmos Simulated Anneling son similares a los algoritmos
Hill Climbing, pero muchas veces ellos aceptan una configuración con un costo alto. La
posibilidad de ir a una configuración de costo alto, depende de una parámetro t, llamado
temperatura . Inicialmente esta temperatura es alta y la posibilidad de que un costo se
incremente es alta. En las iteraciones siguientes la temperatura es decrementada deacuerdo
a el procedimiento de refrescado. El Simulated Annealing clásico comienza en una
configuración arbitraria x. Entonces este genera aleatoriamente una configuración
vecindad y. Si C(y) <= C(x) nosotros escogemos la configuración y. Si C(y) > C(x)
nosotros aceptamos la nueva configuración con la probabilidad exp(C(y)-C(x)/t). Bajo un
apropiado procedimiento de refresqueo este algoritmo converge al global mínimo.
Aplicación de Simulated Anneling a Coloración de Grafos.
Dada una coloración f, c(f) denota el numero de aristas "malas" (u,v) tales
que f(u)=f(v).
Nosotros escogeremos aleatoriamente para cara vértice v en V un color j e K donde K= {
1,2,3,4 ...N } y colorearemos el vértice con el color j escogido. Nosotros
escogemos la coloración f', si c(f') es menor o igual a c(f). Si c(f`) > c(f),
nosotros escogemos la coloración f' con la probabilidad de exp((c(f)-c(f'))/T) y
asignamos a f (la coloración anterior) la probabilidad de 1-exp((c(f)-c(f'))/T).
El problema de Satisfactibilidad
El estudio de algoritmos y problemas que giran alrededor de SAT es una de las áreas
más fascinantes de la computación, debido a que el enfoque está basado en la solución
de problemas que demandan una búsqueda de estado(s) que satisfagan a ciertos
eventos del problema.
El problema llamado SAT , es un problema concerniente a la Lógica Matemática. El enfoque
de SAT es tratar con formulas lógicas que han sido abstraídas de problemas reales.
La solución de SAT consiste en satisfacer con un valor de verdad la conjunción de estas
n cláusulas (Formulas Bien Formadas), las cuales contienen i literales o
proposiciones que pueden ser calificadas con un valor de verdad.
Podemos hacer una analogía con una ecuación de primer grado x+1=2 , donde el objetivo es
averiguar el valor para x, el cual satisfaga el resultado que es 2. Esto es parecido a lo
que es un problema SAT , nada mas que en SAT se busca encontrar asignaciones de verdad en
la mayoría de los casos para muchas literales o proposiciones y los únicos valores que
pueden ser asignados a estas literales son falso o verdadero.
Para resolver los problemas SAT han sido propuestos infinidad de algoritmos los
cuales han sido clasificados por su alcance principalmente en Completos: los que pueden
probar Insatisfactibilidad, y los Incompletos: los que no pueden probar
Insatisfactibilidad y por su eficiencia en las distintas áreas de aplicación. También
se han diseñado técnicas de modelado para llevar un problema especifico de una área
especifica a un problema SAT.
El problema de satisfactibilidad fue el primer problema catalogado como NP-completo
por Stephen Cook en 1971.
¿Por qué resolver el problema de coloración de grafos como un problema SAT?
La idea de atacar el Problema de Coloración de Grafos como un problema de
Satisfactibilidad, viene de ilustrar la diversidad de aplicaciones en el contexto de SAT,
en este caso, el problema de coloración de grafos. Además, existe infinidad de
herramientas (algoritmos), que resuelven eficientemente el problema de Satisfactibilidad,
de manera que si un problema puede ser mapeado a un problema SAT, simplemente aplicaremos
un algoritmo ya existente para obtener resultados.
Es claro que si tenemos un algoritmo que resuelve SAT, podremos solucionar entonces
el problema de coloración de grafos, y como veremos más adelante, el proceso de
reducción de un grafo a cláusulas es muy fácil. Por tanto, consideramos que esta forma
de solucionar coloración de grafos es un método muy fácil de implementar y rápido.
Aplicaciones de la coloración de grafos
Hay numerosas aplicaciones prácticas de coloración de grafos. Incluyendo:
calendarización de exámenes [Wood, 1969]; El diseño y operación de Sistemas de
Manufactura Flexible [Stecke, 1985], y cálculo de elementos Jacobianos dispersos por
diferenciación finita en programación matemática [Coleman y More, 1983].
Desarrollo del trabajo:
Método Propuesto
Dado un grafo cualquiera, generaremos su Matriz de Adyacencia, un vector de tamaño el numero de vértices del grafo. Ya logrado lo anterior, daremos como entrada la información de la Matriz de Adyacencia al Algoritmo Simulated Anneling, escogiendo inicialmente un numero de colores grande, como primera prueba de coloración del grafo, por ejemplo 10, y obteniendo las coloraciones de los vértices respectivas en el vector de resultados. Si la coloración fue posible, se intentara con un numero menor, y se seguirán los mismos pasos, hasta encontrar la aproximación al número cromático. Finalmente, Davis & Putnam intentan colorear el grafo con menos colores a través de particiones binarias. Puede ser que el número encontrado por Simulated Annealing sea el correcto, pero de todas formas Davis & Putnam buscará mejorar el resultado.
Un algoritmo preliminar es:
1. Obtener grafo
2. Generar Matriz de Adyacencia del Grafo
3. Probar una coloración del grafo dado un numero K de colores permitidos usando
Simulated Anneling.
4. Realizar una partición con : x = (Li+Ls)/2
5. ¿es Li=Ls? si, ir a paso 7.
6. Davis & Putnam intenta colorear con x colores. Si lo logra, hacer
Ls = x-1,
de lo contrario, hacer Li=x.
Regresar al paso 4.
7. Obtener Coloración del Grafo, del vector de resultados.
Conclusiones
El empleo del algoritmo de Simulated Anneling en la Coloración de grafos nos proporciona una buena alternativa para acercarnos al número cromático, y Davis & Putnam usandolo en particiones nos ayuda a encontrar el número cromático correcto. De esta manera podremos colorear cualquier grafo correctamente, usando el método propuesto.
Bibliografía
[1] Andreas Nolte y Rainer Scharader [1](Marzo de 1999) “Simulated Anneling and its problems to Color graphs”
[2] M. Chams, A. Hertz, and D. De Werra. “Some experiments with simulated
annealing for coloring graphs”