Algoritmos em Grafos  |  Livros  |  WWW  |  Índice de Termos

 

Coloração de vértices em grafos de intervalos

Em geral, colorir os vértices de um grafo 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  v[0], v[1], v[2], . . . , v[n–1]  de seus vértices tal que, para cada k,

os vértices adjacentes a v[k] em {v[0], . . . , v[k–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 grafos 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).

Por convenção, o grafo não tem laços. Suponha que  v[0], v[1], v[2], . . . , v[n–1]  é uma enumeração dos vértices em ordem crescente de inícios:

i(v[0])  <  i(v[1])  <  i(v[2])  <  . . .   <  i(v[n–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.

2. Mostre que nem todo grafo admite um esquema de eliminação perfeito. (Sugestão: Considere um circuito de comprimento 4 sem diagonais.)

3. 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, r–>próx, r–>próx–>próx, . . . ,  NULL.

4. Desafio [foge ao assunto desse capítulo]:  Escreva uma função C que decida se um grafo dado tem ou não tem um esquema de eliminação perfeito.

5. 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.

Coloração dos vértices

O método de coloração seqüencial 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; uma tal clique prova a otimalidade da coloração.

Exercícios

6. 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.

7. Suponha que  v[0], v[1], v[2], . . . , v[n–1]  é um esquema de eliminação perfeito. Prove que o método seqüencial de coloração produz uma coloração ótima quando aplicado a essa enumeração. 

8. 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.

9. Suponha que  v[0], v[1], v[2], . . . , v[n–1]  é uma enumeração dos vértices de um grafo tal que, para cada k,  os vértices adjacentes a v[k] em {v[0], . . . , v[k–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.