Coloração em Grafos

O Problema da Coloração

Um problema comum que ocorre quando se trabalha com a representação de regiões na forma de mapas coloridos é como representá-las de forma que cada região fique visivelmente clara e distinta das demais. A solução para esse problema se torna possível se para cada região for atribuída uma cor e assim cada uma das regiões teria uma coloração distinta das demais. Mas todo esse esforço em se atribuir uma cor para cada região não é necessário, pois existe uma técnica de coloração de mapas que diz ser possível colorir qualquer mapa planar, utilizando-se apenas quatro cores.



A teoria da coloração de mapas diz ser possível colorir qualquer mapa planar utilizando no mímino quatro cores, sendo para isso necessária a criação de uma lista de adjacência de todos as regiões.
Uma possível abordagem seria representar o problema proposto por uma lista de adjacências onde temos um vetor com as regiões que devem ser coloridas e uma lista com os demais elementos que são as regiões adjacentes a este. Para o mapa representado acima, poderiamos ter a seguinte representação:

Lista de Adjacências para a região A: [B, C, D]
Lista de Adjacências para a região B: [A, C, E]
Lista de Adjacências para a região C: [A, B, D, E, F]
Lista de Adjacências para a região D: [A, C, F]
Lista de Adjacências para a região E: [B, C, F]
Lista de Adjacências para a região F: [C, D, E]

Essa representação diz que as regiões B, C e D são adjacentes a A; as regiões A, C e E são adjacentes a B; as regiões A, B, D, E e F são adjacentes a C; e, analogamente é possível chegar às demais relações.
Sendo assim, o procedimento para se atribuir as cores certas a cada região é o seguinte:
· Escolhe-se uma região inicial, como por exemplo a região A e atribui-se uma cor a ela.
· para atribuir uma cor para B é verificado se dentre as cores existentes, existe uma que não esteja colorindo nenhuma região adjacente a B, então essa cor deverá ser escolhida. Se todas as cores existentes estiverem sendo utilizadas em regiões vizinhas a B, então uma nova cor é criada.
· o raciocínio é repetido analogamente para cada uma das regiões subsequentes.

Assim sendo, pode-se dizer que todas as regiões foram coloridas com a utilização de apenas quatro cores e que essas regiões não possuem nenhuma região vizinha com a mesma cor que ela possui.


Representação através de Grafos

Seja G=(V,E) um grafo e C um conjunto de cores. Uma coloração de G é uma atribuição de alguma cor de C para cada vértice de G, tal que dois vértices adjacentes sempre possuam cores distintas. Formalmente podemos declarar o problema acima como:

Definição: Uma coloração de um grafo G=(V,E) é uma função , onde C é um conjunto de cores, tal que para cada aresta (v,u) de E tem-se . Uma k-coloração de G é uma coloração que utiliza k cores. O número cromático X(G) de um grafo G é o menor número de cores k tal que existe uma k-coloração para G.

Para grafos planares, o problema de coloração está intimamente ligado ao problema das 4 cores em mapas.
Encontrar o número cromático de um grafo é uma tarefa bastante difícil e não é conhecido algoritmo eficiente para realizar esta tarefa. Desta forma tenta-se obter uma aproximação para o problema, objetivando-se encontrar alguma coloração "razoável" para o grafo, i.e., procura-se o número de cores próximo ao número cromático.
Um algoritmo simples para o problema de aproximar o número cromático consiste no seguinte:

Algoritmo: Seleciona-se um vértice de G e atribui-se a ele uma cor 1. No passo geral, os vértices já foram coloridos, sendo k o número de cores utilizadas. Seja Ci o conjunto de vértices que possuem a cor i e considere . Se existir alguma cor i tal que colorimos com a cor i, caso contrário atribuimos a a cor k+1.


Algoritmo de coloração utilizando busca em profundidade.

Algoritmo de coloração utilizando busca em largura.