Introduo Kempe Prog. de Horrios Limites
Teoria dos Grafos - BCC204
Colorao de Grafos
Haroldo Gambini Santos
Universidade Federal de Ouro Preto - UFOP
22 de maio de 2011
1 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Introduo Kempe Prog. de Horrios Limites
Colorao de Mapas
Pergunta
Considere um mapa poltico de qualquer tamanho e com um
nmero qualquer de divises.
Quantas cores so necessrias para pint-lo de modo no
existam dois vizinhos com a mesma cor ?
2 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Introduo Kempe Prog. de Horrios Limites
O Grafo
3 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Notas
Notas
Notas
Introduo Kempe Prog. de Horrios Limites
Exemplos
4 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Introduo Kempe Prog. de Horrios Limites
O Teorema das Quatro Cores
Francis Guthrie
Matemtico (depois botnico)
Aluno do De Morgan
1852: elaborou o teorema e iniciou adiscusso envolvendo:
De MorganHamiltonCayleyCharles Peirce...
a discusso levou a prova de ...
nada.
5 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Introduo Kempe Prog. de Horrios Limites
A Prova de Kempe
Alfred Bray Kempe, orientando de Cayley
1879: Kempe publica uma prova na revistaNature
Torna-se famoso, cavaleiro do ImprioBritnico em 1912
11 anos depois Percy John Heawood publicaum artigo mostrando um erro na prova deKempe.
o artigo, no entanto, prova que pode-secolorir um grafo com 5 cores, usando umaferramenta desenvolvida por Kempe: AsCadeias de Kempe (Kempe Chains)
6 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Notas
Notas
Notas
Introduo Kempe Prog. de Horrios Limites
As Cadeias de Kempe
Idia de vasta utilidade na teoria dos grafos
Considere um n v e duas cores: j e j
Seja Kjj o componente conexo maximal contendo v e nscoloridos com j e j. Kjj chamada uma Cadeia de Kempe.
7 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Introduo Kempe Prog. de Horrios Limites
Exemplo: Programao de Horrios
Tabela indicando alunos matriculados por disciplina:
D.A. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Mat. Port. Ingls Geo. Hist. Fs. Qui. Bio.
8 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Introduo Kempe Prog. de Horrios Limites
Exemplo: Programao de Horrios
O Grafo
9 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Notas
Notas
Notas
Introduo Kempe Prog. de Horrios Limites
Colorao de Grafos
Colorao de Vrtices
Os exemplos anteriormente vistos referem-se ao problema de
Colorao de Vrtices, que o problema mais conhecido de
colorao de grafos.
Nesse problema, pretende-se particionar um grafo em
conjuntos independentes; como todo vrtice constitui um, uma
partio desse tipo sempre existir. Caso se consiga particionar
em k conjuntos independentes diz-se que se tem umak-colorao prpria.
O valor mnimo de k para um dado grafo G o seuNmero Cromtico ou (G).
10 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Introduo Kempe Prog. de Horrios Limites
Aplicaes
Alocao de Registradores
Hierarquia de Memria, ciclos para acesso:
registradores 1 ciclocache 3 ciclos
memria principal at 200 ciclos...
11 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Introduo Kempe Prog. de Horrios Limites
Alocao de Registradores - Exemplo
Instrues Variveis Ativas
ab = a+ 2
a, bc = b b
a, cb = c+ 1
a, breturn b a
a
cb
eax
ebx
cor registrador
12 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Notas
Notas
Notas
Introduo Kempe Prog. de Horrios Limites
Aplicaes
Roteadores wi
O Problema da Interferncia:
um roteador wi pode interferir no sinal de roteadores prximos;nesse caso, devem ser selecionadas freqncias ou canaisdiferentes;o nmero de canais limitado; possvel construir uma rede sem inteferncia com k canais ?
13 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Introduo Kempe Prog. de Horrios Limites
(G) : AlgumasPropriedades
(G) = 1 se e somente se G completamente desconexo;
(G) 3 se e somente se G tem um ciclo mpar; (de modoequivalente, se G no bipartido);
(G) (G) (nmero do clique mximo);(G) (G) + 1 (grau mximo);(G) (G) para G conexo, a no ser que G seja um grafo
completo ou um ciclo mpar;
(G) 4 para qualquer grafo planar: o Teorema das QuatroCores.
14 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Introduo Kempe Prog. de Horrios Limites
Trnsito
15 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Notas
Notas
Notas
Introduo Kempe Prog. de Horrios Limites
Exemplo
ab
c
d
e
16 / 16
Teoria dos Grafos - BCC204, Colorao de Grafos
Notas
Notas
Notas
IntroduoKempeProg. de HorriosLimites
