Aula14_grafos

Prévia do material em texto

Teoria dos Grafos
Valeriano A. de Oliveira
So
orro Rangel
Silvio A. de Araujo
Departamento de Matemáti
a Apli
ada
antunes�ibil
e.unesp.br, so
orro�ibil
e.unesp.br, saraujo�ibil
e.unesp.br
AULA 14
Coloração de Vérti
es
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Coloração de Vérti
es
Coloração de Vérti
es Partição Cromáti
a
Introdução
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
Considere 
ada um dos grafos abaixo:
a) Quantas 
ores são ne
essárias para 
olorir os vérti
es de um grafo de
maneira que dois vérti
es adja
entes não re
ebam a mesma 
or?
b) Qual é o número mínimo de 
ores ne
essárias?
) Considerando as 
ores usadas no item (a) agrupe os vérti
es que
re
eberam a mesma 
or.
d) Pense em algum problema práti
o que vo
e pudesse resolver usando a
partição dos vérti
es obtidas a
ima.
Apli
ações
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
Coloração de mapas - Considere os mapas abaixo:
Qual é o menor número de 
ores ne
essário para pintar os mapas de
forma que duas regiões adja
entes não re
ebam a mesma 
or? Duas
regiões são adja
entes se elas possuem uma linha de fronteira em
omum. Note que no mapa 1 as regiões A e D possuem apenas um
ponto em 
omum e portanto não são adja
entes.
Vamos representar os mapas através de grafos.
Vérti
es - regiões do mapa.
Arestas - existe uma aresta se duas regiões são adja
entes.
Apli
ações
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
Problema das 4 
ores - Quatro 
ores são su�
ientes para 
olorir as
regiões de qualquer mapa sem que duas regiões adja
entes re
ebam a
mesma 
or. Este resultado foi provado 
omputa
ionalmemte em 1976.
Foi um problema proposto em 1852. (Wilson, 1990).
Apli
ações
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
Problema da Coleta de lixo - Uma prefeitura determinou um
onjunto de rotas para a 
oleta de lixo da 
idade. O problema é que as
rotas pré-de�nidas possuem pontos de 
oleta em 
omum. Considere, por
exemplo o 
onjunto de rotas a seguir:
O problema 
onsiste em determinar 
omo dividir o 
onjunto de 6 rotas
em três dias da semana de tal forma que nenhum ponto de 
oleta é
visitado mais que uma vez no mesmo dia.
Apli
ações
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
Representando o problema através de grafos, temos:
- Vérti
es: rotas
- Aresta - existe uma aresta entre duas rotas que possuam pontos de
oleta em 
omum.
Para esta 
onjunto de rotas temos o seguinte grafo:
A partição satisfaz as 
ondições do problema: {A,D}, {B,E}, {C,F}.
Existem outras? É possível fazer a 
oleta em dois dias da semana? O
que muda na solução do problema se as rotas A e F se tornarem uma
rota úni
a? Para formalizar as idéias expostas a
ima 
onsidere:
De�nições
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
De�nição 1. Coloração - Seja G(V,A) um grafo e C=
{c1, c2, c3, ..., cm} um 
onjunto de 
ores. Uma 
oloração de G é uma
atribuição de 
ores aos vérti
es de G de tal forma que dois vérti
es
adja
entes re
ebam 
ores diferentes. O número 
romáti
o de um grafo
G é o menor número de 
ores ne
essário para obter uma 
oloração de G.
Se o número 
romáti
o é χ(G) dizemos que o grafo é χ(G)-
romáti
o.
Como determinar o número 
romáti
o de um grafo? Não é uma tarefa
muito fá
il. Na verdade este é um problema de difí
il resolução no 
aso
de grafos quaisquer, no entanto, para alguns tipos de grafos é possível
resolver o problema fa
ilmente.
De�nições
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 9
Exemplo: Considere os seguintes 
asos:
1. Grafo nulo;
2. Grafo Completo;
3. Grafo 
ir
uito: n ≥ 3, se n é par G é 2-
romáti
o e se n é ímpar G é
3-
romáti
o;
4. Uma árvore é 2-
romáti
o - De�na um vérti
e vj do grafo e atribua
a 
or 1. A partir deste vérti
e, todos os vérti
es que estiverem a
uma distân
ia par atribua a 
or 2 e os que estiverem a uma distân
ia
ímpar atribua a 
or 1. Como existe um e apenas um 
aminho entre
ada par de vérti
es não teremos dois vérti
es adja
entes 
om a
mesma 
or.
De�nições e Teoremas
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
Teorema 2. Um grafo é 2-
romáti
o se e somente se for bipartido.
De�nição 3. Um Clique é um subgrafo 
ompleto de G.
Teorema 4. O número 
romáti
o de um grafo é maior ou igual do que o
tamanho do maior 
lique de G (o tamanho de um 
lique é dado pelo seu
número de vérti
es). Ou seja, o número de vérti
es do maior 
lique do
grafo, Kmax , forne
e um limite inferior para o número 
romáti
o de G.
Exemplo: O grafo a seguir 
ontém um 
lique de tamanho 3. Qual é o
seu número 
romáti
o?
De�nições e Teoremas
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
E um limite superior, 
omo pode ser determinado?
Teorema 5. Se ∆ é grau máximo dos vérti
es de G então o número
romáti
o de G é menor ou igual a ∆+1. Isto é: Kmax ≤ χ(G) ≤ ∆+1
Observação: Observe que para mostrar que um grafo é
χ(G)-
romáti
o, é ne
essário mostrar que usar (χ(G)− 1) 
ores força
dois vérti
es adja
entes a re
eberem a mesma 
or.
Exer
í
io
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
En
ontre o numero 
romáti
o dos grafos a seguir.
a)
b) K7
) K3,5
Partição Cromáti
a
Coloração de Vérti
es Partição Cromáti
a
De�nição
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 14
Seja o grafo G1:
De�nição
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
Uma 
oloração deste grafo, pode ser:
Esta 
oloração parti
iona o 
onjunto de vérti
es do grafo em:
a) {v1}, {v2}, {v3, v4}, {v5}
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 16
Mas vimos ainda que o número 
romáti
o deste grafo é 3 e uma
oloração pode ser:
E a partição asso
iada é:
b) {v1, v5}, {v2}, {v3, v4}
Observe que estes 
onjuntos de vérti
es tem em 
omum o fato que os
vérti
es de um mesmo 
onjunto não são adja
entes.
De�nição
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
De�nição 6. Conjunto Independente - Um sub
onjunto de vérti
es
de um grafo é 
hamado de 
onjunto independente de vérti
e se não
existem dois vérti
es adja
entes neste 
onjunto. Um Conjunto
independente de vérti
es é maximal se nenhum vérti
e pude ser
adi
ionado ao 
onjunto.
Exemplo: Em relação a G1:
onjunto independente: {v1, v5}, {v1}
onjunto independente de vérti
es maximal: {v1, v5}.
Apli
ação
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 18
Suponha que o grafo G2:
des
reve o seguinte problema. Cada um dos sete vérti
es é uma palavra
ódigo a ser usada em algum tipo de 
omuni
ação. Algumas dessas
palavras são pare
idas 
om outras (por exemplo, em relação ao som) e
podem ser 
onfundidas. Tais pares de palavras são ligadas por arestas.
En
ontre o maior 
onjunto possível de palavras 
ódigo que podem ser
usadas para se obter uma 
omuni
ação segura.
{a, c, d, f} é uma solução: 
onjunto independente de vérti
es maximal.Apli
ação
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
Este grafo possue 5 
onjuntos independentes de vérti
es maximais:
{a, c, d, f}, {a, c, d, g}, {b, g}, {b, f}, {a, e}
qual é o número 
romáti
o do grafo? É o menor número de 
onjuntos
independentes 
uja união 
ontém todos os vérti
es do grafo. Por
exemplo:
{a, c, d, f}, {b, g}, {a, e}.
Assim o problema de determinar uma 
oloração mínima de G pode ser
formulado em termos de parti
ionar V em um número mínimo de
onjuntos independentes.
De�nição
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
De�nição 7. Partição Cromáti
a Dado um grafo 
onexo, simples, a
partição do 
onjunto de vérti
es no menor número possível de 
onjuntos
independentes de vérti
es é 
hamada de partição 
romáti
a.
Exemplo:
{(a, c, d, f), (b, g), (e)}
{(a, c, d, g), (b, f), (e)}
{(c, d, f), (b, g), (a, e)}
{(c, d, g), (b, f), (a, e)}
São 4 exemplos de partições 
romáti
as do grafo G2.
Algoritmo Guloso de Coloração
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
Como en
ontrar uma partição 
romáti
a de um grafo? Vamos ver a
seguir um algoritmo guloso (ou míope) baseado na idéia de 
onstrução
de 
onjuntos independentes.
1. Dado um grafo G(V,A).
2. Iní
io
3. Ordene o 
onjunto de vérti
es em ordem não 
res
ente de graus:
v1, v2, ..., vn.
4. Faça S1 = S2 = ... = Sn = ∅
5. In
lua v1 em S1.
6. Para j = 2, ..., n faça:
en
ontre o 
onjunto Sr, tal que o vérti
e vj não seja adja
ente a
nenhum vérti
e já in
luído a ele e r = min{i, i = 1, ..., n}.
In
lua o vérti
e vj em Sr.
7. Fim
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
Note que ao �m do algoritmo teremos obtido no máximo n 
onjuntos
independentes de vérti
es. Vamos usar esta idéia para obter uma
partição 
romáti
a do grafo G3.
Ordenação dos vérti
es: {2, 3, 5, 6, 7, 8, 1, 4, 8, 10}
Partição: S1 = {2, 5, 9}; S2 = {3, 7, 1}; S3 = {6, 10}; S4 = {8, 4}
Outra partição: S1 = {2, 4, 9}; S2 = {1, 3, 7}; S2 = {6, 10};
S4 = {5, 8}.
Apli
ação
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 23
O senado possui várias 
omissões que se reúnem durante uma hora por
semana. Deseja-se fazer um 
alendário de reuniões que minimiza o
número total de horas de reuniões e tal que duas 
omissões que possuam
membros em 
omum não se reúnam no mesmo horário. Supondo que
existem 10 
omissões mostre que este problema pode ser resolvido 
omo
um problema de 
oloração.
Se as 
omissões não possuíssem membros em 
omum elas poderiam se
reunir simultaneamente. Como resolver então? A informação 
have é o
fato de que um mesmo membro perten
em a mais de uma 
omissão.
Para representar o problema através de um grafo, pre
isamos de�nir os
vérti
es e as arestas. Sejam as 
omissões os vérti
es. E as arestas vão
ligar 
omissões que possuem membros em 
omum. Vamos supor que o
grafo abaixo representa uma situação parti
ular
Apli
ação
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 24
Para de�nir um 
alendário de reuniões basta en
ontrar o número
romáti
o deste grafo e uma 
oloração asso
iada.
Exer
í
ios
Coloração de Vérti
es Partição Cromáti
a
Teoria dos Grafos (Antunes Rangel&Araujo) � 25
1) Modele o problema de en
ontrar o número 
romáti
o de G utilizando
variáveis 0/1.
2) En
ontre um grafo tal que o número 
romáti
o seja 2 mas que a
oloração obtida através do algoritmo guloso des
rito a
ima é maior ou
igual a 3.
3) Qual é o número 
romáti
o do mapa do Brasil?
(ver em: A. Rabelo, M. Moreira e S. Rangel, O número 
romáti
o do
Brasil, Anais do CNMAC 2010, SBMAC, disponível em
http://www.sbma
.org.br/eventos/
nma
/xxxiiicnmac/pdf/691.pdf
(última visita 08/01/2015).
	Coloração de Vértices
	Introdução
	Aplicações
	Aplicações
	Aplicações
	Aplicações
	Definições
	Definições
	Definições e Teoremas
	Definições e Teoremas
	Exercício
	Partição Cromática
	Definição
	Definição
	
	Definição
	Aplicação
	Aplicação
	Definição
	Algoritmo Guloso de Coloração
	
	Aplicação
	Aplicação
	Exercícios