TEMA_5_-_ARA0175_-_GRAFOS_PLANARES_E_COLORA__O

Prévia do material em texto

Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
TEMA 5 – GRAFOS PLANARES E COLORAÇÃO
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
GRAFOS PLANARES
Grafos Planares – Introdução
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 3
Dado um grafo 𝐺, é possível encontrar uma representação gráfica para o grafo 
tal que não haja cruzamento de arestas?
Grafos Planares – Introdução
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 4
Dado um grafo 𝐺, é possível encontrar uma representação gráfica para o grafo 
tal que não haja cruzamento de arestas?
Grafo 𝐴 Grafo 𝐵 Grafo C
Grafos Planares – Introdução
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 5
Dado um grafo 𝐺, é possível encontrar uma representação gráfica para o grafo 
tal que não haja cruzamento de arestas?
Planar do 
Grafo 𝐴′
Planar do 
Grafo 𝐵′
Planar do 
Grafo C′
Grafos Planares – Definição
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 6
Definição 1. Um grafo 𝐺 é dito planar se puder ser representado graficamente 
no plano de tal forma que não haja cruzamento de suas arestas. Caso contrário 
o grafo é dito não-planar. 
Grafos Planares – Definição
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 7
Definição 1. Um grafo 𝐺 é dito planar se puder ser representado graficamente 
no plano de tal forma que não haja cruzamento de suas arestas. Caso contrário 
o grafo é dito não-planar. 
Grafo 𝐴
Grafo 𝐵
Grafo 𝐶
Os grafos dos 1º 
exemplos anteriores são 
grafos planares.
Grafos Planares – Definição
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 8
Definição 1. Um grafo 𝐺 é dito planar se puder ser representado graficamente 
no plano de tal forma que não haja cruzamento de suas arestas. Caso contrário 
o grafo é dito não-planar. 
Os grafos dos 2º 
exemplos anteriores são 
grafos planos.
Planar do 
Grafo 𝐴′
Planar do 
Grafo 𝐵′
Planar do 
Grafo C′
Grafos Planares – Definição
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 9
Definição 1. Um grafo 𝐺 é dito planar se puder ser representado graficamente 
no plano de tal forma que não haja cruzamento de suas arestas. Caso contrário 
o grafo é dito não-planar. 
Observação: Se existir uma representação do grafo em uma superfície 
sem que haja cruzamento de arestas, dizemos que existe uma imersão 
do grafo na superfície.
Grafos Planares – Definição
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 10
Como podemos determinar se um grafo é planar?
Grafos Planares – Definição
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 11
Como podemos determinar se um grafo é planar?
Existem dois grafos não planares que são muito importantes no estudo de 
planaridade. Estes dois grafos são chamados Grafos de Kuratowski.
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 12
Teorema 1. O grafo 𝐾5 é um grafo não planar.
4
2 3
5
1
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 13
Teorema 1. O grafo 𝐾5 é um grafo não planar.
4
2 3
5
1
Vamos acrescentar 
aresta (𝑣2, 𝑣3).
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 14
Teorema 1. O grafo 𝐾5 é um grafo não planar.
4
2 3
5
1
Agora vamos 
acrescentar aresta 
(𝑣2, 𝑣5).
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 15
Teorema 1. O grafo 𝐾5 é um grafo não planar.
4
2 3
5
1 Agora vamos acrescentar 
aresta (𝑣4, 𝑣1). Como 
queremos manter a 
planaridade, inserimos “por 
fora”.
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 16
Teorema 1. O grafo 𝐾5 é um grafo não planar.
4
2 3
5
1
Vamos acrescentar aresta (𝑣4, 𝑣3). 
Como queremos manter a 
planaridade, inserimos “por fora”.
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 17
Teorema 1. O grafo 𝐾5 é um grafo não planar.
4
2 3
5
1
Ao tentar acrescentar aresta 
(𝑣1, 𝑣5), não será possível inserir 
sem que haja cruzamento.
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 18
Teorema 1. O grafo 𝐾5 é um grafo não planar.
4
2 3
5
1
Ao tentar acrescentar aresta 
(𝑣1, 𝑣5), não será possível inserir 
sem que haja cruzamento.
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 19
Teorema 1. O grafo 𝐾5 é um grafo não planar.
4
2 3
5
1
Ao tentar acrescentar aresta 
(𝑣1, 𝑣5), não será possível inserir 
sem que haja cruzamento.
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 20
Teorema 2. O grafo 𝐾3,3 é um grafo não planar.
4
2 3
5
1
6
𝐾3,3 
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 21
Teorema 2. O grafo 𝐾3,3 é um grafo não planar.
4
2 3
5
1
6
Redesenhando, vamos tentar 
acrescentar aresta (𝑣3, 𝑣4), não 
será possível inserir sem que haja 
cruzamento.
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 22
Teorema 2. O grafo 𝐾3,3 é um grafo não planar.
4
2 3
5
1
6
Redesenhando, vamos tentar 
acrescentar aresta (𝑣3, 𝑣4), não 
será possível inserir sem que haja 
cruzamento.
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 23
Teorema 2. O grafo 𝐾3,3 é um grafo não planar.
4
2 3
5
1
6
Redesenhando, vamos tentar 
acrescentar aresta (𝑣3, 𝑣4), não 
será possível inserir sem que haja 
cruzamento.
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 24
Teorema 2. O grafo 𝐾3,3 é um grafo não planar.
4
2 3
5
1
6
Redesenhando, vamos tentar 
acrescentar aresta (𝑣3, 𝑣4), não 
será possível inserir sem que haja 
cruzamento.
Grafos Planares – Características
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 25
Teorema de Kuratowski. Um grafo que é dito planar não pode apresentar nem 
o grafo completo 𝐾5 nem o grafo bipartido 𝐾3,3 como subgrafos. 
Demonstração. A prova de que o 𝐾3,3 não é planar pode ser feita de duas 
formas: por indução e por construção, enquanto a do 𝐾5 é feita apenas por 
construção.
Grafos Planares – Aplicações 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 26
Aplicações da Planaridade em Grafos
• Circuitos integrados 
• Circuitos impressos (placas onde componentes eletrônicos são 
montados)
• Rodovias conectando cidades
• Linhas de transmissão de energia elétrica
• Linha de produção em uma indústria 
Grafos Planares – Aplicações 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 27
Aplicações da Planaridade em Grafos
• Circuitos integrados 
• Circuitos impressos (placas onde componentes eletrônicos são 
montados)
• Rodovias conectando cidades
• Linhas de transmissão de energia elétrica
• Linha de produção em uma indústria 
Grafos Planares – Aplicações 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 28
Aplicações da Planaridade em Grafos
• Circuitos integrados 
• Circuitos impressos (placas onde componentes eletrônicos são 
montados)
• Rodovias conectando cidades
• Linhas de transmissão de energia elétrica
• Linha de produção em uma indústria 
Grafos Planares – Aplicações 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 29
Aplicações da Planaridade em Grafos
• Circuitos integrados 
• Circuitos impressos (placas onde componentes eletrônicos são 
montados)
• Rodovias conectando cidades
• Linhas de transmissão de energia elétrica
• Linha de produção em uma indústria 
Grafos Planares – Aplicações 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 30
Aplicações da Planaridade em Grafos
• Circuitos integrados 
• Circuitos impressos (placas onde componentes eletrônicos são 
montados)
• Rodovias conectando cidades
• Linhas de transmissão de energia elétrica
• Linha de produção em uma indústria 
Grafos Planares – Aplicações 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 31
Aplicações da Planaridade em Grafos
• Circuitos integrados 
• Circuitos impressos (placas onde componentes eletrônicos são 
montados)
• Rodovias conectando cidades
• Linhas de transmissão de energia elétrica
• Linha de produção em uma indústria 
Grafos Planares – Regiões 
Prof. Simone 
Gama
ALGORITMOSEM GRAFOS 32
Regiões de um Plano
A representação planar de um grafo divide o plano em regiões, no qual 
uma região é ilimitada.
Grafos Planares – Regiões 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 33
Regiões de um Plano
A representação planar de um grafo divide o plano em regiões, no qual 
uma região é ilimitada.
Exemplo 1:
Grafos Planares – Regiões 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 34
Regiões de um Plano
A representação planar de um grafo divide o plano em regiões, no qual 
uma região é ilimitada.
Exemplo 2: Exemplo 3:
Grafos Planares – Regiões 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 35
Regiões de um Plano
Definição 2. Se 𝐺 é um grafo planar, então toda representação planar de 
𝐺 divide o plano em regiões, chamadas faces.
Grafos Planares – Regiões 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 36
Regiões de um Plano
Definição 2. Se 𝐺 é um grafo planar, então toda representação planar de 
𝐺 divide o plano em regiões, chamadas faces.
Observação:
• Uma das faces é ilimitada, e é chamada face infinita. 
• Se 𝑓 é uma face qualquer, o grau de 𝑓, denotado por 𝑑(𝑓), é igual ao 
número de arestas contida na trilha fechada que a define. 
Grafos Planares – Regiões 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 37
Regiões de um Plano
Definição 2. Se 𝐺 é um grafo planar, então toda representação planar de 
𝐺 divide o plano em regiões, chamadas faces.
Exemplo 5:
O grafo possui 4 faces e:
𝑑(𝑓1) = 8 
𝑑(𝑓2) = 3 
𝑑(𝑓3) = 9 
𝑑(𝑓4) = 4 
Grafos Planares – Fórmula de Euler 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 38
Teorema 3. Se 𝐺 é um grafo conexo planar com 𝒎 arestas e 𝒏 vértices, então 
qualquer representação planar de 𝐺 possui 𝒇 = 𝒎 − 𝒏 + 𝟐 faces.
Grafos Planares – Fórmula de Euler 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 39
Teorema 3. Se 𝐺 é um grafo conexo planar com 𝒎 arestas e 𝒏 vértices, então 
qualquer representação planar de 𝐺 possui 𝒇 = 𝒎 − 𝒏 + 𝟐 faces.
Exemplo 6:
𝒇 = 𝒎 − 𝒏 + 𝟐
𝑓 = 12 − 10 + 2
𝒇 = 𝟒 
Grafos Planares – Fórmula de Euler 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 40
Teorema 3. Se 𝐺 é um grafo conexo planar com 𝒎 arestas e 𝒏 vértices, então 
qualquer representação planar de 𝐺 possui 𝒇 = 𝒎 − 𝒏 + 𝟐 faces.
Exemplo 7:
𝒇 = 𝒎 − 𝒏 + 𝟐
𝑓 = 12 − 8 + 2
𝒇 = 𝟔 
Grafos Planares – Fórmula de Euler 
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 41
Teorema 3. Se 𝐺 é um grafo conexo planar com 𝒎 arestas e 𝒏 vértices, então 
qualquer representação planar de 𝐺 possui 𝒇 = 𝒎 − 𝒏 + 𝟐 faces.
Exemplo 7:
𝒇 = 𝒎 − 𝒏 + 𝟐
𝑓 = 12 − 8 + 2
𝒇 = 𝟔 
𝑓1
𝑓2
𝑓3
𝑓4 𝑓5
𝑓6
Grafos Planares – Exercícios
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 42
1. Desenhe os grafos abaixo de tal forma que sejam planos, se possível.
2. Sendo os grafos acima planares, calcule através da fórmula de Euler o números de 
faces de cada um.
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
COLORAÇÃO EM GRAFOS PLANARES
Características em Grafos - Cliques
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 44
Um clique em um grafo não-dirigido é um conjunto de vértices dois a dois 
adjacentes.
Em outras palavras, um conjunto 𝐶 de vértices é um clique se para todo 
par 𝑣, 𝑤 de vértices distintos em 𝐶, existe uma aresta com pontas 𝑣 e 𝑤.
i
ii
i
i
i
i i
Características em Grafos - Cliques
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 45
i
i
i
i i
Um clique em um grafo não-dirigido é um conjunto de vértices dois a dois 
adjacentes.
Em outras palavras, um conjunto 𝐶 de vértices é um clique se para todo 
par 𝑣, 𝑤 de vértices distintos em 𝐶, existe uma aresta com pontas 𝑣 e 𝑤.
Características em Grafos - Cliques
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 46
i
i i
Um clique em um grafo não-dirigido é um conjunto de vértices dois a dois 
adjacentes.
Em outras palavras, um conjunto 𝐶 de vértices é um clique se para todo 
par 𝑣, 𝑤 de vértices distintos em 𝐶, existe uma aresta com pontas 𝑣 e 𝑤.
Características em Grafos – Conj. Independente
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 47
Um conjunto independente é um conjunto de vértices que não são 
adjacentes entre si.
Características em Grafos – Conj. Independente
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 48
Um conjunto independente é um conjunto de vértices que não são 
adjacentes entre si.
Grafos Planares – Mapas
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 49
Grafos Planares são amplamente utilizados para representar mapas:
Exemplo 1:
Mapa 1 Mapa 2
Grafos Planares – Mapas
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 50
Grafos Planares são amplamente utilizados para representar mapas:
Exemplo 1:
Mapa 1 Mapa 2
B
A
C D
G
F
E
E
A
B
C
D
Cada região é 
um vértice.
Grafos Planares – Mapas
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 51
Grafos Planares são amplamente utilizados para representar mapas:
Exemplo 1:
Mapa 1 Mapa 2
B
A F
A
B
C
D
Cada vizinhança 
existe aresta.
C D
G
E
E
Grafos Planares – Coloração de Mapas
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 52
Como colorir um mapa é um problema usual e clássico, daí surgiu o 
problema de colorir um grafo, já que um grafo planar representa um mapa.
Mapa 1 Mapa 2
Grafos Planares – Coloração de Mapas
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 53
Mapa 2
Como colorir um mapa é um problema usual e clássico, daí surgiu o 
problema de colorir um grafo, já que um grafo planar representa um mapa.
Mapa 1
Grafos Planares – Coloração de Mapas
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 54
Problema da Coloração de Mapas
Para colorir um mapa, devemos seguir 
algumas restrições, onde regiões que são 
vizinhas recebem cores diferentes, para 
que essas regiões não conflitem na 
visualização do mapa:
Grafos Planares – Coloração de Mapas
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 55
Problema da Coloração de Mapas
Para colorir um mapa, devemos seguir 
algumas restrições, onde regiões que são 
vizinhas recebem cores diferentes, para 
que essas regiões não conflitem na 
visualização do mapa:
Grafos Planares – Coloração de Mapas
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 56
Problema da Coloração de Mapas
Para colorir um mapa, devemos seguir 
algumas restrições, onde regiões que são 
vizinhas recebem cores diferentes, para 
que essas regiões não conflitem na 
visualização do mapa.
Além dessa restrição, podemos inserir uma 
questão de otimização: Qual a quantidade 
mínima de cores posso colorir um mapa?
Grafos Planares – Coloração de Mapas
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 57
Problema da Coloração de Mapas
Para colorir um mapa, devemos seguir 
algumas restrições, onde regiões que são 
vizinhas recebem cores diferentes, para 
que essas regiões não conflitem na 
visualização do mapa.
Além dessa restrição, podemos inserir uma 
questão de otimização: Qual a quantidade 
mínima de cores posso colorir um mapa?
Observe que podemos colorir o 
mapa acima com no mínimo 3 
cores.
Grafos Planares – Coloração de Mapas
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 58
Problema das Quatro cores
As questões que acabamos de ver foram necessárias para o surgimento de 
um problema clássico em computação: Problema das Quatro cores.
Quatro cores são suficientes para colorir as regiões de qualquer mapa sem 
que duas regiões adjacentes recebam a mesma cor.
Problema das Quatro cores
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 59
Histórico
1852
A conjectura foi proposta 
pela primeira vez por Francis 
Guthrie, quando tentava 
colorir o mapa dos condados 
da Inglaterra
1878
A primeira 
referência sobre o 
Teorema das 
Quatro Cores 
publicada é de 
Arthur Cayley.
Alfred Kempe 
anunciou na 
revista Nature que 
tinha uma 
demonstração da 
conjectura.
1879
1880
Outra prova do 
Teorema das 
Quatro Cores, 
feita por Peter 
Guthrie Tait.
1890
Percy Heawood 
mostra que a 
prova de Kempe 
estava errada e 
ainda provo 
Teorema das 5 
cores.
Julius Petersen 
mostra que 
estava 
incorreta a 
provade Tait.
1891
1976
O Teorema das Quatro Cores foi 
finalmente provado por 
Kenneth Appel e Haken 
Wolfgang na Universidade de 
Illinois. Usaram mais de 1.200 
horas do computador mais 
rápido que havia para 
demonstrar a conjectura. 
1997
Robertson, 
Sanders, 
Seymour e 
Thomas também 
provaram usando 
computador.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 60
Definição 1. Uma coloração de um grafo simples é o rotulamento de uma 
cor a cada vértice do grafo tal que dois vértices adjacentes não possuem a 
mesma cor. 
Problema das Quatro cores: Definições
Exemplo 2:
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 61
Definição 2. Dizemos que um grafo é 𝒌-colorível se tem uma coloração 
válida com 𝑘 cores.
Problema das Quatro cores: Definições
3-colorível
Exemplo 3:
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 62
Definição 3. O número cromático de um grafo é o menor número de cores 
necessárias à coloração deste grafo. O número cromático de um grafo 𝐺 é 
denotado por 𝜒(𝐺).
Problema das Quatro cores: Definições
𝜒(𝐺) = 3
Exemplo 4:
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 63
Problema das Quatro cores: Definições
Resumo:
𝜒(𝐺) = 3
Também podemos dizer que o grafo é 3-cromático.
3-colorível
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 64
Problema da Coloração de Grafos: Definições
Problema da coloração em algumas classes de grafos
Grafos Árvores e Grafos Bipartidos são 
2-cromáticos.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 65
Problema da Coloração de Grafos: Definições
Grafos Árvores e Grafos Bipartidos são 
2-cromáticos.
Grafos Ciclos 𝐶𝑛 com 𝑛 
par são 2-cromáticos.
Grafos Ciclos 𝐶𝑛 com 𝑛 
ímpar são 3-cromáticos.
Problema da coloração em algumas classes de grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 66
Problema da Coloração de Grafos: Definições
Determine o número cromático de:
• Grafo nulo: 𝜒(𝐺) =
• Grafo completo: 𝜒(𝐾𝑛) =
• Grafo caminho: 𝜒 𝑃𝑛 =
Problema da coloração em algumas classes de grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 67
Problema da Coloração de Grafos: Limites
É possível determinar limitantes de coloração para facilitar a determinação 
da coloração em vértices de grafos.
Limites para Coloração de Vértices em Grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 68
Problema da Coloração de Grafos: Limites
Limites para Coloração de Vértices em Grafos
Todo grafo com clique 𝜔, a 
coloração 𝜔(𝐺) ≤ 𝜒(𝐺).
1º Limite inferior
• 𝜔(𝐺) = tamanho da maior clique em 𝐺.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 69
Problema da Coloração de Grafos: Limites
1º Limite inferior
• 𝜔(𝐺) = tamanho da maior clique em 𝐺.
Limites para Coloração de Vértices em Grafos
Todo grafo com clique 𝜔, a 
coloração 𝜔(𝐺) ≤ 𝜒(𝐺).
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 70
Problema da Coloração de Grafos: Limites
2º Limite inferior
• Se Δ o grau máximo dos vértices de 𝐺. Então 𝜒 𝐺 ≤ 1 + Δ.
Limites para Coloração de Vértices em Grafos
Δ = 2
𝜒 𝐺 = 2
Δ = 3
𝜒 𝐺 = 3
Δ = 3
𝜒 𝐺 = 4
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 71
Problema da Coloração de Grafos: Limites
3º Limite inferior
• Seja (𝐺) o número do maior conjunto independente de 𝐺. Então o 
conjunto de vértices desse conjunto é colorido com uma (1) cor e a 
quantidade de conjuntos independentes define a quantidade de cores de 
𝐺.
Limites para Coloração de Vértices em Grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 72
Problema da Coloração de Grafos: Limites
3º Limite inferior
• Seja (𝐺) o número do maior conjunto independente de 𝐺. Então o 
conjunto de vértices desse conjunto é colorido com uma (1) cor e a 
quantidade de conjuntos independentes define a quantidade de cores de 
𝐺.
Limites para Coloração de Vértices em Grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 73
Problema da Coloração de Grafos: Aplicações
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 74
Problema da Coloração de Grafos: Aplicações
1ª Aplicação: Atribuição de frequências de rádio
1. Vértices: Os vértices representam os transmissores das estações de rádio. 
2. Arestas: 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 frequência. 
3. Cores: Cada cor contém estações que podem 
receber a mesma frequência.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 75
Problema da Coloração de Grafos: Aplicações
2ª Aplicação: Alocação de Registradores
Considere a expressão 𝑏2 − 4 ∗ 𝑎 ∗ 𝑐 e seguinte trecho de código assembly para 
resolver a expressão:
1. r1 = b * b
2. r2 = 4 * a
3. r2 = r2 * c
4. r1 = r1 - r2
Fonte: http://www.uel.br/cce/dc/wp-
content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf 
http://www.uel.br/cce/dc/wp-content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf
http://www.uel.br/cce/dc/wp-content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 76
Problema da Coloração de Grafos: Aplicações
2ª Aplicação: Alocação de Registradores
Considere a expressão 𝑏2 − 4 ∗ 𝑎 ∗ 𝑐 e seguinte trecho de código assembly para 
resolver a expressão:
1. r1 = b * b
2. r2 = 4 * a
3. r2 = r2 * c
4. r1 = r1 - r2
r1 r2
a c
b
Os vértices representam o 
registrador virtual, que contém as 
variáveis da memória (local físico). Fonte: http://www.uel.br/cce/dc/wp-
content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf 
http://www.uel.br/cce/dc/wp-content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf
http://www.uel.br/cce/dc/wp-content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 77
Problema da Coloração de Grafos: Aplicações
2ª Aplicação: Alocação de Registradores
Considere a expressão 𝑏2 − 4 ∗ 𝑎 ∗ 𝑐 e seguinte trecho de código assembly para 
resolver a expressão:
1. r1 = b * b
2. r2 = 4 * a
3. r2 = r2 * c
4. r1 = r1 - r2
r1 r2
a c
b
As arestas representam as colisões 
entre as variáveis que precisam 
coexistir no mesmo intervalo. Fonte: http://www.uel.br/cce/dc/wp-
content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf 
http://www.uel.br/cce/dc/wp-content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf
http://www.uel.br/cce/dc/wp-content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 78
Problema da Coloração de Grafos: Aplicações
2ª Aplicação: Alocação de Registradores
Considere a expressão 𝑏2 − 4 ∗ 𝑎 ∗ 𝑐 e seguinte trecho de código assembly para 
resolver a expressão:
1. r1 = b * b
2. r2 = 4 * a
3. r2 = r2 * c
4. r1 = r1 - r2
r1 r2
a c
b
A variável r1 
coexiste em todo 
intervalo do 
trecho do 
programa!
Fonte: http://www.uel.br/cce/dc/wp-
content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf 
http://www.uel.br/cce/dc/wp-content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf
http://www.uel.br/cce/dc/wp-content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 79
Problema da Coloração de Grafos: Aplicações
2ª Aplicação: Alocação de Registradores
Considere a expressão 𝑏2 − 4 ∗ 𝑎 ∗ 𝑐 e seguinte trecho de código assembly para 
resolver a expressão:
1. r1 = b * b
2. r2 = 4 * a
3. r2 = r2 * c
4. r1 = r1 - r2
r1 r2
a c
b
As cores representam os 
registradores físicos no 
qual as variáveis físicas 
serão alocados.
green blue red
r1 b a r2 c Fonte: http://www.uel.br/cce/dc/wp-
content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf 
http://www.uel.br/cce/dc/wp-content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf
http://www.uel.br/cce/dc/wp-content/uploads/TCC_BANCA_TALLYS_OLIVEIRA_MION.pdf
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 80
Problema da Coloração de Grafos: Aplicações
3ª Aplicação: Sudoku
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 81
Problema da Coloração de Grafos: Aplicações
3ª Aplicação: Sudoku
Cada célula representa um vértice e 
existe uma aresta entre dois vértices se 
eles estão em uma mesma linha, mesma 
coluna ou no mesmo bloco.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 82
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 83
Problemada Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos
Temos uma péssima notícia...
Não existe algoritmo de tempo polinomial que resolva o problema da 𝒌-
coloração em grafos...
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 84
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos
• (Garey e Johnson, 1974): O problema de achar o número cromático de 
um grafo é NP-difícil. 
• O algoritmo de força bruta busca por uma 𝑘 -coloração de 𝐺 
considerando cada uma das 𝑘𝑛 atribuições possíveis e checa se cada 
uma delas é correta.
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 85
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Força Bruta
1
2
3
1
2
3
1
2
3
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 86
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Força Bruta
1
2
3
1
2
3
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 87
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Força Bruta

1
2
3
1
2
3
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 88
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Força Bruta

1
2
3

1
2
3
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 89
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Força Bruta

1
2
3
1
2
3
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 90
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Força Bruta

1
2
3
1
2
3
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 91
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Força Bruta

1
2
3
1
2
3
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 92
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Força Bruta

1
2
3
1
2
3
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 93
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Força Bruta

1
2
3
 
2
1
2
3
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 94
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Força Bruta
 
2
 
3
1
2
3
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 95
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Heurística
• Algoritmo de Welsh-Powell
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 96
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Heurística
• Algoritmo de Welsh-Powell
b e c d g f a h
3 3 2 2 2 2 1 1
Ordenação dos vértices por grau
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 97
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Heurística
• Algoritmo de Welsh-Powell
b e c d g f a h
3 3 2 2 2 2 1 1
Ordenação dos vértices por grau
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 98
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Heurística
• Algoritmo de Welsh-Powell
b e c d g f a h
3 3 2 2 2 2 1 1
Ordenação dos vértices por grau
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 99
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Heurística
• Algoritmo de Welsh-Powell
b e c d g f a h
3 3 2 2 2 2 1 1
Ordenação dos vértices por grau
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 100
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Heurística
• Algoritmo de Welsh-Powell
Ordenação dos vértices por grau
b e c d g f a h
3 3 2 2 2 2 1 1
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 101
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Heurística
• Algoritmo de Welsh-Powell
Ordenação dos vértices por grau
b e c d g f a h
3 3 2 2 2 2 1 1
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 102
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Heurística
• Algoritmo de Welsh-Powell
Ordenação dos vértices por grau
b e c d g f a h
3 3 2 2 2 2 1 1
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 103
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Heurística
• Algoritmo de Welsh-Powell
Ordenação dos vértices por grau
b e c d g f a h
3 3 2 2 2 2 1 1
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 104
Problema da Coloração de Grafos: Algoritmos
Algoritmos em Coloração de Grafos – Heurística
• Algoritmo de Welsh-Powell
Ordenação dos vértices por grau
b e c d g f a h
3 3 2 2 2 2 1 1
Dúvidas?
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 105
Bibliografia
• Algoritmos Coloração em Grafos: 
• Adaptado de Jayme Luiz. Estruturas de Dados e seus Algoritmos. Rio de Janeiro: LTC, 
1994.
• Adaptado das aulas Prof Dr. Eduardo Nakamura, Universidade Federal do Amazonas 
(ICOMP- UFAM) – AM.
• Adaptado das aulas Prof. Dr Fábio Protti, Universidade Federal Fluminense (IC-UFF) – 
Niterói, RJ.
• Adaptado das aulas Análise de Algoritmos - Prof Ms. Simone Gama, Universidade 
Federal do Amazonas (ICOMP- UFAM - FUCAPI) – AM.
• Fonte das figuras: 
• Grafos planares e regiões: https://homepages.dcc.ufmg.br/~loureiro/md/md_9Grafos_MaterialExtra
Prof. Simone 
Gama
ALGORITMOS EM GRAFOS 106
https://homepages.dcc.ufmg.br/~loureiro/md/md_9Grafos_MaterialExtra
	Slide 1: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 2: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 3: Grafos Planares – Introdução
	Slide 4: Grafos Planares – Introdução
	Slide 5: Grafos Planares – Introdução
	Slide 6: Grafos Planares – Definição
	Slide 7: Grafos Planares – Definição
	Slide 8: Grafos Planares – Definição
	Slide 9: Grafos Planares – Definição
	Slide 10: Grafos Planares – Definição
	Slide 11: Grafos Planares – Definição
	Slide 12: Grafos Planares – Características
	Slide 13: Grafos Planares – Características
	Slide 14: Grafos Planares – Características
	Slide 15: Grafos Planares – Características
	Slide 16: Grafos Planares – Características
	Slide 17: Grafos Planares – Características
	Slide 18: Grafos Planares – Características
	Slide 19: Grafos Planares – Características
	Slide 20: Grafos Planares – Características
	Slide 21: Grafos Planares – Características
	Slide 22: Grafos Planares – Características
	Slide 23: Grafos Planares – Características
	Slide 24: Grafos Planares – Características
	Slide 25: Grafos Planares – Características
	Slide 26: Grafos Planares – Aplicações 
	Slide 27: Grafos Planares – Aplicações 
	Slide 28: Grafos Planares – Aplicações 
	Slide 29: Grafos Planares – Aplicações 
	Slide 30: Grafos Planares – Aplicações 
	Slide 31: Grafos Planares – Aplicações 
	Slide 32: Grafos Planares – Regiões 
	Slide 33: Grafos Planares – Regiões 
	Slide 34: Grafos Planares – Regiões 
	Slide 35: Grafos Planares – Regiões 
	Slide 36: Grafos Planares – Regiões 
	Slide 37: Grafos Planares – Regiões 
	Slide 38: Grafos Planares – Fórmula de Euler 
	Slide 39: Grafos Planares – Fórmula de Euler 
	Slide 40: Grafos Planares – Fórmula de Euler 
	Slide 41: Grafos Planares – Fórmula de Euler 
	Slide 42: Grafos Planares – Exercícios
	Slide 43: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 44: Características em Grafos - Cliques
	Slide 45: Características em Grafos - Cliques
	Slide 46: Características em Grafos - Cliques
	Slide 47: Características em Grafos – Conj. Independente
	Slide 48: Características em Grafos – Conj. Independente
	Slide 49: Grafos Planares – Mapas
	Slide 50: Grafos Planares – Mapas
	Slide 51: Grafos Planares – Mapas
	Slide 52: Grafos Planares – Coloração de Mapas
	Slide 53: Grafos Planares – Coloração de Mapas
	Slide 54: Grafos Planares – Coloração de Mapas
	Slide 55: Grafos Planares – Coloração de Mapas
	Slide 56: Grafos Planares – Coloração de Mapas
	Slide 57: Grafos Planares – Coloração de Mapas
	Slide 58: Grafos Planares – Coloração de Mapas
	Slide 59: Problema das Quatro cores
	Slide 60: Problema das Quatro cores: Definições
	Slide 61: Problema das Quatro cores: Definições
	Slide 62: Problema das Quatro cores: Definições
	Slide 63: Problema das Quatro cores: Definições
	Slide 64: Problemada Coloração de Grafos: Definições
	Slide 65: Problema da Coloração de Grafos: Definições
	Slide 66: Problema da Coloração de Grafos: Definições
	Slide 67: Problema da Coloração de Grafos: Limites
	Slide 68: Problema da Coloração de Grafos: Limites
	Slide 69: Problema da Coloração de Grafos: Limites
	Slide 70: Problema da Coloração de Grafos: Limites
	Slide 71: Problema da Coloração de Grafos: Limites
	Slide 72: Problema da Coloração de Grafos: Limites
	Slide 73: Problema da Coloração de Grafos: Aplicações
	Slide 74: Problema da Coloração de Grafos: Aplicações
	Slide 75: Problema da Coloração de Grafos: Aplicações
	Slide 76: Problema da Coloração de Grafos: Aplicações
	Slide 77: Problema da Coloração de Grafos: Aplicações
	Slide 78: Problema da Coloração de Grafos: Aplicações
	Slide 79: Problema da Coloração de Grafos: Aplicações
	Slide 80: Problema da Coloração de Grafos: Aplicações
	Slide 81: Problema da Coloração de Grafos: Aplicações
	Slide 82: Problema da Coloração de Grafos: Algoritmos
	Slide 83: Problema da Coloração de Grafos: Algoritmos
	Slide 84: Problema da Coloração de Grafos: Algoritmos
	Slide 85: Problema da Coloração de Grafos: Algoritmos
	Slide 86: Problema da Coloração de Grafos: Algoritmos
	Slide 87: Problema da Coloração de Grafos: Algoritmos
	Slide 88: Problema da Coloração de Grafos: Algoritmos
	Slide 89: Problema da Coloração de Grafos: Algoritmos
	Slide 90: Problema da Coloração de Grafos: Algoritmos
	Slide 91: Problema da Coloração de Grafos: Algoritmos
	Slide 92: Problema da Coloração de Grafos: Algoritmos
	Slide 93: Problema da Coloração de Grafos: Algoritmos
	Slide 94: Problema da Coloração de Grafos: Algoritmos
	Slide 95: Problema da Coloração de Grafos: Algoritmos
	Slide 96: Problema da Coloração de Grafos: Algoritmos
	Slide 97: Problema da Coloração de Grafos: Algoritmos
	Slide 98: Problema da Coloração de Grafos: Algoritmos
	Slide 99: Problema da Coloração de Grafos: Algoritmos
	Slide 100: Problema da Coloração de Grafos: Algoritmos
	Slide 101: Problema da Coloração de Grafos: Algoritmos
	Slide 102: Problema da Coloração de Grafos: Algoritmos
	Slide 103: Problema da Coloração de Grafos: Algoritmos
	Slide 104: Problema da Coloração de Grafos: Algoritmos
	Slide 105: Dúvidas?
	Slide 106: Bibliografia