Problemas de Coloração em Grafos

Transcrição

Problema das Quatro Cores
Coloração de Vértices
Teoria dos Grafos
Problemas de Coloração em Grafos
Profa. Sheila Morais de Almeida
DAINF-UTFPR-PG
abril - 2016
1
2
Caminhos e Ciclos
Grafos bipartidos
Grafos completos
Limites para χ(G )
• Um dos problemas mais famosos da Teoria dos Grafos.
• Origem em 1852 com a conjectura de Francis Guthrie.
Conjectura das Quatro Cores
Todo mapa pode ser colorido com quatro cores, de forma que
regiões vizinhas tenham cores distintas.
• Duas regiões são vizinhas se compartilham uma linha de
fronteira composta por mais que um único ponto do mapa.
• O Problema das Quatro Cores consiste em determinar a
veracidade da Conjectura das Quatro Cores.
Desde meados do século 19 e por todo o século 20, este problema
foi objeto de estudo de matemáticos ilustres:
Augustus de Morgan, Willian Rowan Hamilton, Arthur Cayley,
James Joseph Sylvester, August Möbius, Peter Guthrie Tait,
George David Birkhoff, William T. Tutte, Robin Thomas e outros.
Tudo começou quando Francis Guthrie (1831 - 1899) observou que
podia colorir o mapa da Inglaterra com quatro cores e conjecturou
que não precisaria de mais que quatro cores para colorir qualquer
mapa.
Francis contou sua conjectura ao irmão, Frederick Guthrie (1833 1886).
Frederick contou a conjectura do irmão ao seu professor de
matematica, o famoso Augustus De Morgan (1806 - 1871), na
University Colege London.
Em abril de 1860, anonimamente, o Problema das Quatro Cores foi
publicado no periódico Athenaeum. Esse texto tornou o Problema
das Quatro Cores conhecido nos Estados Unidos.
De Morgan foi professor do britânico James Joseph Sylvester (1814
- 1897), que desenvolveu pesquisas com Arthur Cayley (1821 1895).
Em 1878, Cayley falou sobre o Problema das Quatro Cores em um
encontro da London Mathematical Society.
Alfred Bray Kempe (1849 - 1922) estava presente no encontro da
London Mathematical Society e ouviu Cayley falar do problema.
Em 1879, Kempre apresentou uma prova da Conjectura do
Problema das Quatro Cores, aceita tanto na Inglaterra quanto nos
Estados Unidos.
Por esse feito, Kempe tornou-se membro da Royal Society, em
1881.
Para resolver o Problema das Quatro Cores, Kempe o modelou
como um grafo, onde cada região é representada por um vértice e
existe uma aresta uv se as regiões representadas pelos vértices u e
v são vizinhas no mapa.
O grafo obtido a partir de um mapa é chamado de grafo dual.
Observe que todo grafo dual é conexo e planar.
Observe também que se considerarmos que o grafo dual é um
mapa e fizermos o seu dual, obtemos o mapa original.
Kempe mostrou que o Problema das Quatro Cores é equivalente
ao problema de determinar se um grafo pode ter seus vértices
coloridos utilizando-se quatro cores, de forma que vértices vizinhos
tenham cores distintas.
Problema da Coloração de Vértices
Dado um grafo, qual o menor número de cores necessárias para se
colorir seus vértices de forma que vértices vizinhos tenham cores
distintas?
Kempe definiu um mapa normal como um mapa onde não podem
haver mais do que três regiões se encontrando em um ponto, e
nenhuma região inclui outra.
Ele argumentou que se houver um mapa que requer cinco cores,
então deve haver um mapa normal que tenha o menor número de
regiões dos mapas que requerem cinco cores para serem coloridos,
que é chamado de um mapa minimal cinco-cromático.
Ele mostrou que todo mapa contém um paı́s com cinco ou menos
paı́ses adjacentes.
Lema
Se G é um grafo simples, conexo e planar com três ou mais
vértices, então existe pelo menos um vértice com grau menor ou
igual a 5.
Demonstração: Suponha, por contradição, que todo vértice em G
tem grau maior que 5, isto é, grau 6 ou maior.
Então a soma dos graus dos vértices é pelo menos 6n.
Como a soma dos graus dos vértices é igual a 2m, 6n ≤ 2m.
Como G é planar, conexo e com pelo menos três vértices, deve
satisfazer a desigualdade m ≤ 3n − 6, ou seja, 2m ≤ 6n − 6.
Então 6n ≤ 2m ≤ 6n − 6, um absurdo!
Então há um pequeno conjunto de configurações inevitáveis, isto é,
de arranjos de regiões, pelo menos uma das quais deve ocorrer em
todo mapa normal.
Kempe assumiu, então, a existência de um mapa cinco-cromático
normal (que ocorreria se existisse qualquer mapa que requer cinco
cores para sua coloração).
Kempe argumentou que qualquer configuração inevitável deste
mapa leva a uma contradição.
Percy John Heawood (1861 - 1955) leu o artigo de Kempe com a
prova do Teorema das Quatro Cores.
Em 1890, 10 anos após a apresentação da prova de Kempe ,
Heawood publicou um artigo com um mapa para o qual os
argumentos de Kempe não eram corretos.
Heawood refutou a prova de Kempe.
Heawood também provou que qualquer mapa pode ser colorido
com cinco cores de forma que regiões que compartilham uma linha
de fronteira tenham cores distintas.
Teorema das Cinco Cores O número cromático de um grafo
conexo, simples e planar é no máximo 5.
Prova: A prova é por indução no número de vértices.
Base: n ≤ 5.
5 cores são suficientes para colorir grafo que tem até 5 vértices. 3
Hipótese de indução: qualquer grafo simples, conexo e planar
com até k vértices pode ser colorido com cinco cores.
Passo: Seja G um grafo com as mesmas caracterı́sticas com
k + 1 vértices.
Podemos assumir que k + 1 ≥ 6, pois os casos de cinco ou menos
vértices já foram tratados.
Sabemos que existe um vértice v com d(v ) ≤ 5.
Remova v do grafo G .
O grafo G − v pode ser desconexo, é simples, planar e cada
componente tem no máximo k vértices.
v
v
Pela hipótese de indução, cada subgrafo conexo maximal tem uma
coloração com no máximo cinco cores (use as mesmas cinco cores
para colorir cada subgrafo).
Reinsira v e suas arestas no grafo. Se d(v ) ≤ 5 ou se seus vizinho
não usam as cinco cores, existe uma cor disponı́vel para colorir v .
v
Pela hipótese de indução, cada subgrafo conexo maximal tem uma
coloração com no máximo cinco cores (use as mesmas cinco cores
para colorir cada subgrafo).
Reinsira v e suas arestas no grafo. Se d(v ) ≤ 5 ou se seus vizinho
não usam as cinco cores, existe uma cor disponı́vel para colorir v .
v
Considere então o caso em que v tem grau 5 e seus vizinhos estão
coloridos com 5 cores diferentes.
v3
v2
v
v4
v5
v1
Imagine que os vizinhos com cores diferentes estão numerados
v1 , v2 , . . . , v5 .
Considere todos os vértices do grafo coloridos com as cores 1 ou 3.
Suponha que não exista caminho usando esses vértices conectando
v1 a v3 .
v
Considere todos os vértices do grafo coloridos com as cores 1 ou 3.
Suponha que não exista caminho usando esses vértices conectando
v1 a v3 .
v1
v2
v5
v
v4
v3
Então, ao considerarmos os vértices com cores 1 e 3, existem duas
componentes disjuntas do grafo, uma contendo v1 e outra
contendo v3 .
v1
v2
v5
v
v4
v3
Na componente que contém v1 , trocamos as cores 1 e 3 de todos
os vértices.
Isto não viola a coloração dos subgrafos, v1 passa a ter a cor 3 e a
cor 1 pode ser usada em v .
v1
v3
os vértices.
v1
v3
os vértices.
v1
v2
v5
v
v4
v3
os vértices.
v1
v2
v5
v
v4
v3
Por outro lado, se existe um caminho entre v1 e v3 usando apenas
os vértices de cores 1 e 3...
v1
v5
v
v2
v4
v3
v1
v3
v1
v3
Se existe um caminho entre v1 e v3 usando apenas os vértices de
cores 1 e 3, consideramos todos os vértices do grafo que têm cores
2 e 4.
Será que existe um caminho entre v2 e v4 usando apenas vértices
com cores 2 e 4? Não!
v1
v5
v
v2
v4
v3
Se existe um caminho entre v1 e v3 usando apenas os vértices de
cores 1 e 3, consideramos todos os vértices do grafo que têm cores
2 e 4.
Será que existe um caminho entre v2 e v4 usando apenas vértices
com cores 2 e 4? Não!
v1
v5
v
v2
v4
v3
Devido à arrumação dos vértices v1 , v2 , v3 , v4 e v5 , este caminho
deveria cruzar o caminho que conecta v1 e v3 .
Como o grafo é planar, estes dois caminhos teriam que se
encontrar em um vértice, que teria que ter as cores 1 ou 3 em
função do caminho v1 –v3 e as cores 2 ou 4 em função do caminho
v2 –v4 , um absurdo.
Portanto, não há caminho que use apenas os vértices coloridos
com 2 ou 4 entre v2 e v4 .
Podemos rearrumar as cores como no caso anterior e colorir v . Problema das Quatro Cores
v1
v5
v
v2
v4
v3
v1
v5
v
v2
v4
v3
O Problema das Quatro Cores permaneceu sem solução até 1976,
quase 100 anos após a prova de Kempe, quando Haken e Appel
provaram que a conjectura é, de fato, verdadeira.
Haken e Appel, usando um computador, construı́ram finalmente
um conjunto de 1482 configurações inevitáveis.
Eles mostraram que qualquer dessas configurações que faça parte
de um mapa cinco-cromático normal leva a uma contradição.
Portanto, nenhum mapa requer cinco cores.
Teorema das Quatro Cores Qualquer mapa pode ser colorido
com quatro cores de forma que regiões que compartilham uma
linha de fronteira tem cores distintas.
Coloração de vértices
Da prova de Kemp surgiu o Problema da Coloração de Vértices.
Uma coloração de vértices é uma atribuição de cores para os
vértices de um grafo G .
Uma coloração de vértices é válida se vértices adjacentes tem
cores diferentes.
Uma coloração de vértices é ótima se é uma coloração válida que
utiliza o menor número de cores possı́vel.
Problema da Coloração de Vértices
Dado um grafo G , qual o menor número de cores com o qual se
pode colorir todos os vértives de G de forma que vértices
adjacentes tenham cores distintas?
O menor número de cores que permite uma coloração ótima de G
é chamado de número cromático de G , denotado por χ(G ).
Coloração de vértices em Caminhos e Ciclos
Nos caminhos:
χ(Pn ) = 2
Nos ciclos:
χ(Cn ) = 2, se n é par;
χ(Cn ) = 3, se n é ı́mpar.
Coloração de vértices em grafos Bipartidos
χ(B) = 2, pela própria definição de bipartidos.
Observe que em qualquer coloração de vértices válida, cada classe
de cor é um conjunto independente.
Coloração de vértices em grafos completos
χ(Kn ) = n.
Limites para χ(G )
Um limite inferior para o número cromático é o tamanho da maior
clique.
ω(G ): tamanho da maior clique em G .
χ(G ) ≥ ω(G )
Um grafo G é perfeito se χ(G ) = ω(G ).
Limites para χ(G )
Limite superior: χ(G ) ≥ ∆(G ) + 1 (algoritmo guloso)
Teorema (Brooks, 1941) Se G é conexo, simples e não é
completo, nem ciclo ı́mpar, χ(G ) ≤ ∆(G ).

Problemas de Coloração em Grafos

Transcrição

Documentos relacionados

Método Bonecas Russas para Conjunto Independente

Exercicios 3 - Departamento de Matemática - PUC-Rio

Conexidade e Distância

livro de colorir

Análise de Redes Sociais

UNIVERSIDADE FEDERAL DE MINAS GERAIS DEPARTAMENTO

Baixar desenhos - Turma do Parque

Cap´ıtulo 6 Grafos - Parte II (Algoritmos)

Atividades Para Colorir - Backyardigans

Livros para Colorir : Livro para Colorir - Hot Wheels