coloração de grafo

TP3 - Colora¸ca˜o de Grafo
C´
assio Elias dos Santos Jr ([e-mail])
Ciˆencia da Computa¸ca˜o - Universidade Federal de Minas Gerais
24 de novembro de 2014

Resumo
Este documento tem por objetivo o estudo da modelagem de problemas do tipo NP-Completo usando grafos e a pr´atica de paradigmas de programa¸c˜ao. O problema ´e referente a colora¸c˜ao de grafos: dado um grafo G(V, E), devemos colorir cada v´ertice V com o m´ınimo de cores de forma que nenhum v´ertice adjacente receba a mesma cor. Para isto, estudamos primeiramente o problema e em seguida desenvolvemos um algoritmo usando o paradigma de tentativa e erro, branch and bound e um algoritmo aproximado usando o paradigma guloso. Constru´ımos ent˜ ao um programa na linguagem de programa¸c˜ao C e realizamos alguns testes para comparar os algoritmos que fizemos em termos de custo computacional e qualidade dos resultados. Enfim, apresentamos os resultados dos testes e conclu´ımos com uma compara¸c˜ao dos algoritmos.

1

Introdu¸ c˜ ao

Problemas semelhantes ao de colora¸c˜ao de grafos s˜ao comuns na computa¸c˜ao.
Geralmente ocorrem em otimiza¸c˜oes e problemas combinat´orios. Podemos citar como exemplo dividir um grupo de pessoas para uma entrevista com alguns gerentes de forma que n˜ ao exista conflito de hor´ario entre elas. Neste caso as pessoas seriam v´ertices do grafo e conflitos de hor´ario entre duas pessoas s˜ao arestas. Dividimos o estudo neste documento em 3 se¸c˜oes: a primeira ´e justamente esta e trata de introduzir o problema ao leitor; a segunda, se¸c˜ao 2, colocamos uma descri¸c˜ ao detalhada e formal do problema de colora¸c˜ao de grafos. Descrevemos na se¸c˜ ao 3 alguns algoritmos usando os paradigmas da computa¸c˜ao tentativa e erro, branch and bound e guloso. Constru´ımos o programa na se¸c˜ao
4 explicitando as estruturas de dados utilizadas, o formato de entrada e sa´ıda.
Enfim, na se¸c˜ ao 5, apresentamos os resultados de alguns testes e