Heurística matemática aplicada ao problema da coloração de grafos.

Abstract

Dado um grafo G = (V, E) composto por um conjunto de vértices V e um conjunto de arestas E, o Problema da Coloração de Grafos (PCG) consiste em atribuir uma cor a cada vértice do grafo, de modo que vértices adjacentes não possuam a mesma cor, utilizando o menor número de cores possível. Esse é um dos problemas mais estudados na área de Otimização Combinatória devido a suas inúmeras aplicações. Este trabalho propõe a aplicação de uma heurística matemática, mipHeuristic, baseada em decomposição para resolver o Problema da Coloração de Grafos, faz uma comparação dos resultados da heurística matemática proposta com algoritmos já consagrados na literatura, como a heurística de refinamento recol e a meta-heurística Simulated Aneealing, e apresenta a análise dos resultados obtidos em relação ao estado da arte. Os resultados obtidos sugerem que a heurística matemática mipHeuristic funciona melhor quando aplicada à instâncias menores e que a utilização de heurísticas matemáticas para o Problema da Coloração de Grafos (PCG) apresenta resultados promissores.