Recoloração convexa de grafos

Resumo

Dados um grafo G=(V,E), um conjunto de cores e uma coloração que define uma cor para os vértices de G, dizemos que a coloração é convexa se cada classe de cor induz um subgrafo conexo. Quando uma coloração não é convexa, é importante saber qual o menor número de recolorações são necessárias para alcançar essa propriedade. Uma recoloração convexa mínima é uma coloração obtida a partir de uma coloração não convexa com o menor número de vértices com cores trocadas. Esse problema surgiu a partir do estudo de árvores filogenéticas, em que a convexidade indica que não houveram convergências ou reversões durante a evolução de uma característica. Além da aplicação na biologia, o problema também pode ser aplicado a redes de computadores com poucas modificações. Neste projeto, estudaremos o problema com árvores e grafos gerais. Para isso, desenvolveremos algoritmos com a meta-heurística GRASP e modelos matemáticos para as versões estudadas do problema. Por fim, serão realizados experimentos com os algortimos e modelos desenvolvidos neste trabalho e os presentes na literatura, a fim de comparar desempenho e qualidade da solução. (AU)