Autores

6317
2866,6,414
6318
2866,6,414
6319
2866,6,414

Informações:

Publicações do PESC

Título
Algoritmos Exatos para Problema de Coloração em Grafos
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
22/12/2005
Resumo

Colorir um grafo significa pintar cada um dos seus vértices com uma cor, de forma tal que, se dois vértices quaisquer são adjacentes, então eles recebem cores distintas. Neste trabalho, realizamos um estudo sob forma de levantamento entre os diversos métodos que solucionam, de maneira exata, o problema de encontrar o número mínimo de cores, chamado número cromático, necessárias para colorir um grafo qualquer. Além deste, analisamos os algoritmos exatos para outros dois problemas de coloração em grafos: a 3-coloração e a 4-coloração. Propomos ainda, um novo algoritmo para verificar se um grafo pode ser colorido com três cores.

Abstract

To color a graph means painting each of its vertices with some color, in such a way that whenever two vertices are adjacent they receive different colors. In the preseilt work, we survey some of the different exact methods described in the literature, for coloriilg a graph using the miniinuin possible number of colors - the chromatic number of the graph. In addition, we also study the existing exact methods for the problems of 3-coloring and 4-coloring. Fiilally, we propose a new algorithm for solving the 3-coloring problein.

Arquivo
Topo