Coloração de vértices de grafos de intervalos
Em geral,
colorir os vértices de um grafo não-dirigido
com número mínimo de cores é difícil.
Para certas classes de grafos, entretanto,
o problema é relativamente fácil.
Esse capítulo cuida de uma dessas classes.
Esquema de eliminação perfeito
Um esquema de eliminação perfeito
(= perfect elimination scheme)
para um grafo não-dirigido sem laços
é qualquer enumeração
v0,
v1,
v2, … ,
vn−1
de seus vértices tal que, para cada k,
os vizinhos de vk em
{ v0, … ,
vk−1 }
são todos adjacentes entre si.
É claro que nem todo grafo
não-dirigido sem laços admite um esquema de eliminação perfeito
(a bem da verdade, grafos que têm um tal esquema são raros).
Exemplo importante: grafos de intervalos.
Suponha que os vértices do meu grafo não-dirigido
são intervalos (de tempo, por exemplo).
Assim, cada vértice v do grafo
tem um início i(v)
e um fim f (v).
Dois vértices v e w são adjacentes se
os correspondentes intervalos
têm um ponto em comum, ou seja, se
i(v) fica entre
i(w) e f (w)
ou
i(w) fica entre i(v) e
f (v).
Os intervalos são distinos dois a dois e portanto o grafo não tem laços.
Suponha agora que
v0,
v1,
v2, … ,
vn−1
é uma enumeração dos vértices
em ordem crescente de inícios:
i(v0) ≤
i(v1) ≤
i(v2) ≤ … ≤
i(vn−1).
Essa enumeração é um esquema de eliminação perfeito.
Exercícios 1
-
Mostre que a enumeração dos vértices de um grafo de intervalos
em ordem crescente de inícios
é um esquema de eliminação perfeito.
-
Mostre que nem todo grafo admite um esquema de eliminação perfeito.
(Sugestão: Considere um circuito de comprimento 4 sem diagonais.)
-
Escreva uma função C que decida se uma enumeração dos
vértices de um grafo não-dirigido sem laços
é ou não é um esquema de eliminação perfeito.
Suponha que a enumeração dos vértices é dada por uma lista
r,
rprox,
rproxprox, … ,
NULL.
-
Escreva uma função (recursiva) C
que tente encontrar um esquema de eliminação perfeito
em um grafo G.
Use o seguinte roteiro:
encontre um vértice v cujo conjunto de vizinhos
seja uma clique;
em seguida, aplique o processo ao grafo G−v.
-
[Desafio]
Escreva uma função C que decida se um grafo dado
tem ou não tem um esquema de eliminação perfeito.
Coloração dos vértices
O método de coloração sequencial
aplicado a um esquema de eliminação perfeito
produz uma coloração ótima
(ou seja, com número mínimo de cores).
Mais que isso:
junto com a coloração dos vértices,
o método produz uma clique que tem tamanho igual
ao número de cores
e portanto prova a otimalidade da coloração.
Exercícios 2
-
Suponha que
v0,
v1,
v2, … ,
vn−1
é um esquema de eliminação perfeito.
Prove que o método sequencial
de coloração produz uma coloração ótima
quando aplicado a essa enumeração.
-
Escreva uma função C que receba um grafo
e um esquema de eliminação perfeito
e devolva uma coloração ótima dos vértices e uma clique
de tamanho igual ao número de cores.
-
Um certo conjunto de eventos
quer usar um centro de convenções.
Cada evento tem uma data de início e uma data de fim.
O centro não pode atender dois eventos simultâneos.
Encontre um conjunto máximo de eventos que o centro de convenções pode
atender.
-
Suponha que
v0,
v1,
v2, … ,
vn−1
é uma enumeração dos vértices de um grafo tal que,
para cada k,
os vértices adjacentes a vk em
{ v0, … ,
vk−1 }
são todos não-adjacentes entre si.
Mostre como colorir os vértices com
número de cores igual ao tamanho de uma clique.