u
n
e
s
p
Coloração de Grafos
Ronaldo Celso Messias Correia
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
O Problema da Coloração
 A teoria da coloração de mapas diz ser possível colorir
qualquer mapa planar utilizando no mínimo quatro
cores
 Em 1976, usando grafos, Haken e Appel apresentaram
uma solução
Estruturas de Dados – Listas de Adjacências:
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]
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
O Problema da Coloraçã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
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.
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
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:

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.
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Aplicações da Coloração
 Quando uma aplicação é modelada como um problema
de coloração de vértices, os vértices em cada classe
de cores representam indivíduos ou itens que não
competem ou conflitam entre si




Atribuição de freqüências de rádio
Separação de produtos explosivos
Agendamento de cursos na universidade
Alocação de registros para programação
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Atribuição de frequências de rádio:
 Os vértices representam os transmissores das
estações de rádio
 Duas estações são adjacentes quando suas áreas de
transmissão se sobrepõem, o que resultaria em
interferência se elas usassem a mesma freqüência
 Cada cor contém estações que podem receber a
mesma frequência
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Separação de produtos explosivos:
 Os vértices representam produtos químicos
necessários em algum processo de produção
 Existe uma aresta ligando cada par de produtos que
podem explodir, se combinados
 O número cromático representa o número mínimo de
compartimentos para guardar estes produtos químicos
em segurança
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Agendamento de cursos na universidade:
 Os vértices representam os cursos de uma
universidade
 Dois cursos são adjacentes se um aluno se matricula
para ambos os cursos
 O número cromático representa o número mínimo de
horários necessários para acomodar os cursos
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Alocação de registradores para programação:
 Os vértices representam as variáveis a serem alocadas
nos registradores de execução rápida
 Duas variáveis são adjacentes se elas podem estar
ativas ao mesmo tempo
 O número cromático representa o número mínimo de
registradores necessários para evitar o problema de
overswapping
Ronaldo Celso Messias Correia – [email protected]
Algoritmo de Coloração
u
n
e
s
p
O algoritmo abaixo produz rapidamente
uma coloração própria para qualquer
grafo:
Entrada: um grafo G com lista de vértices v1, v2, ..., vp
Saída: uma coloração própria de vértices f: VG  {1,2, ...}
Algoritmo: Coloração Seqüencial de Vértices
para i = 1 até p
Seja f(vi) = o menor número de cor não usado nos
vizinhos de menor índice de vi
retorne coloração de vértices f
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Algoritmo de Coloração utilizando busca em
profundidade
Programa Principal
montar a lista de adjacências
inicializar a estrutura de cores
escolher o vertice Vi de maior grau para ser colorido primeiro
chamar a sub-rotina Colore_Vertice para colorir o vertice Vi escolhido
Sub-rotina Colore_Vertice: Vk
se o vertice Vk ainda nao foi colorido
procurar a cor C apropriada
se nao existir cor apropriada para colorir o vertice Vk
criar uma nova cor C
fim se
colorir o vertice Vk com a cor C
para todo vertice Vj adjacente a Vk faça
chamar a sub-rotina Colore_Vertice para colorir o vertice Vj
Fim se
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Algoritmo de Coloração utilizando busca em profundidade
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Algoritmo de Coloração utilizando busca em largura
Programa Principal
montar a lista de adjacências
inicializar a estrutura de cores
inicializar a estrutura de fila
escolher o vertice Vi de maior grau para ser colorido primeiro
chamar a sub-rotina Colore_Vertice para colorir o vertice Vi escolhido
inserir o vertice Vi na fila Q
enquanto a fila Q nao estiver vazia faca
remove o vertice Vk da fila
para todo vertice Vj adjacente a Vk faça
chamar a sub-rotina Colore_Vertice para colorir o vertice Vj
inserir Vj na fila
fim para
fim enquanto
Sub-rotina Colore_Vertice: Vk
se o vertice Vk ainda nao foi colorido
procurar a cor C apropriada
se nao existir cor apropriada para colorir o vertice Vk
criar uma nova cor C
fim se
colorir o vertice VkRonaldo
com aCelso
corMessias
C
Correia – [email protected]
fim se
u
n
e
s
p
Algoritmo de Coloração utilizando busca em
profundidade
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Exercícios
 Implementar os algoritmos de coloração utilizando
busca em profundidade
 Implementar os algoritmos de coloração utilizando
busca em largura
Ronaldo Celso Messias Correia – [email protected]