PROBLEMA E ALGORITMOS DE COLORAÇÃO EM GRAFOS - EXATOS E HEURÍSTICOS

Resumo

Contexto: Dados um grafo G e um inteiro k > 0 , o problema da coloração em grafos consiste em utilizar um conjunto de n <= k cores para atribuir a cada vértice de G uma determinada cor, de modo que vértices adjacentes tenham cores distintas. A despeito da existência de métodos de exatos, capazes de determinar a solução do problema de coloração, observa-se que estas técnicas possuem em alguns casos complexidade exponencial. A limitação apresentada pelos métodos exatos quando aplicados a instâncias de maior complexidade motivou o desenvolvimento de diversas heurísticas, aptas a indicar soluções de maneira satisfatória para grafos em geral. Este trabalho descreve o problema da coloração em grafos, apresenta algumas das técnicas que podem ser utilizadas na sua determinação, além de enumerar alguns problemas reais que podem ser modelados a partir de um grafo G e solucionados com base no resultado alcançado pela aplicação de uma coloração sobre G.