Coloração de vértices

(Veja Graph coloring na Wikipedia.)

Uma coloração dos vértices de um grafo não-dirigido é uma atribuição de cores aos vértices que tenha a seguinte propriedade: as pontas de cada aresta têm cores diferentes. [Favor não confundir o conceito de coloração de vértices com as marcas branco, cinza, preto que usamos em outra ocasião para acompanhar a evolução de algoritmos de busca.] É evidente que um grafo admite coloração de vértices se e só se não tem laço algum.

É fácil produzir uma coloração com muitas cores: basta atribuir uma cor diferente para cada vértice. É mais difícil obter uma coloração com poucas cores.

Problema da Coloração de Vértices: Dado um grafo não-dirigido, encontrar uma coloração dos vértices com número mínimo de cores.

Dizemos que uma coloração é ótima se o número de cores é mínimo. O problema também pode ser apresentado assim:

Problema: Dado um grafo não-dirigido e um número k, encontrar uma coloração dos vértices que use k ou menos cores.

Exercícios

Faça uma coloração ótima dos vértices do grafo complete(8). Esse é o grafo não-dirigido completo de 8 vértices. A macro complete(n) está definida no módulo GB_BASIC do SGB (bloco 7) e significa board(n,0,0,0,-1,0,0). Por sua vez, board gera os movimentos de uma peça de xadrez (verdadeira ou imaginária) num tabuleiro (verdadeiro ou imaginário).
Faça uma coloração ótima dos vértices do grafo circuit(7). Esse é o circuito não-dirigido com 7 vértices. A macro circuit(n) está definida no módulo GB_BASIC do SGB (bloco 7) e significa board(n,0,0,0,1,1,0).
Faça uma coloração ótima dos vértices do grafo disjoint_subsets(5,2). Esse é o grafo de Petersen. A macro disjoint_subsets(n,k) está definida no módulo GB_BASIC do SGB (bloco 36) e significa subsets(k,1,1-n,0,0,0,1,0).
[Bom!] Encontre uma coloração ótima dos vértices do grafo product(circuit(5),circuit(3),2,0) . A função product está definida no bloco 94 do módulo GB_BASIC do SGB.
Suponha que cada vértice v de um grafo não-dirigido tem uma cor v–>cor (os valores possíveis de cor são 0, 1, 2, etc.). Escreva uma função C que decide se os rótulos definem uma coloração dos vértices. Em caso afirmativo, a função deve devolver o número de cores usadas pela coloração.

Cobertura por conjuntos estáveis

Uma cobertura por conjuntos estáveis é uma coleção E1, E2, . . , Ek de conjuntos estáveis tal que cada vértice do grafo pertence a algum Ei, ou seja, tal que a união de E1, E2, . . , Ek seja o conjunto de todos os vértices do grafo.

Uma cobertura por conjuntos estáveis é o mesmo que uma coloração de vértices: cada Ei corresponde a uma cor. [Nossa definição de cobertura permite que um vértice pertença a dois conjuntos estáveis diferentes, ou seja, tenha duas cores diferentes. Mas isso não é importante: se Ei intercepta Ej, basta trocar Ei por Ei – Ej e observar que esse último conjunto também é estável.] Portanto, nosso problema pode ser reformulado assim:

Problema da Coloração de Vértices: Cobrir um grafo não-dirigido com o menor número possível de conjuntos estáveis.

Exercícios

Suponha que E1, E2, . . , Ek é uma cobertura de um grafo não-dirigido por conjuntos estáveis. É verdade que cada Ei é um conjunto estável máximo? É verdade que cada Ei é um conjunto estável maximal?
[Simples mas Importante] Suponha que nosso grafo tem uma clique com k vértices. Mostre que toda coloração dos vértices usa pelo menos k cores. Em outras palavras, mostre que em qualquer grafo, o número de cores de qualquer coloração é maior ou igual que o tamanho de qualquer clique. Dê exemplos de grafos em que o número de cores de uma coloração ótima é estritamente maior que o tamanho da maior clique.

Discuta o seguinte algoritmo. Ele resolve o problema da coloração com número mínimo de cores?

for (v = v0; v < vn; v++) v–>cor = 1;
k = 0;
do {
   flag = 0;
   k++;
   for (v = v0; v < vn; v++) {
      if (v–>cor != k) continue;
      for (a = v–>arcs; a != NULL; a = a–>next) {
         if (a–>tip–>cor == k) {
            a–>tip–>cor = k+1;
            flag = 1; } } }
} while (flag == 1);

Heurísticas

Não sei escrever um algoritmo eficiente que resolva o problema da coloração ótima de qualquer grafo não-dirigido. Mas posso tentar algumas heurísticas, ou seja, algoritmos que às vezes produzem colorações com poucas cores, mas não oferecem nenhuma garantia disso.

A base de muitas heurísticas é o seguinte método de coloração seqüencial dos vértices. Suponha dada uma enumeração dos vértices do grafo, ou seja, uma seqüência v[0], v[1], . . . , v[n–1] em que cada vértice aparece uma e uma só vez. [Essa enumeração não tem relação alguma com a ordem em que os vértices aparecem no vetor g–>vertices da estrutura de dados do SGB.] Para determinar uma coloração dos vértices a partir dessa enumeração basta fazer o seguinte (supondo que o grafo não tem laços):

0
1
2
3
4
5
6
7
8
9

k = 0
para j = 0 até n–1 faça
D = {1, . . . , k}
para i = 0 até j–1 faça
se v[i] é adjacente a v[j]
então D = D – {cor[v[i]]}
se D não é vazio
então cor[v[j]] = min D
senão k = k+1
senão cor[v[j]] = k

No início de cada execução do bloco de linhas 2-9, temos cores 1, . . , k e os vértices v[0], v[1], . . . , v[j–1] já estão coloridos. O bloco de linhas 3-9 atribui a menor cor possível a v[j].

Exercícios

Implemente uma versão do método de coloração seqüencial de vértices. Use a ordem em que os vértices aparecem no vetor g–>vertices da estrutura de dados do SGB. Suponha que o grafo não tem laços (o usuário terá que verificar essa condição antes de chamar a função).
Implemente o método de coloração seqüencial de vértices. A enumeração dos vértices que servirá de base para a coloração é dada pela lista encadeada v, v–>prox, v–>prox–>prox, etc.
Suponha dado um grafo não-dirigido sem laços. Suponha que v[0], v[1], . . . , v[n–1] é uma enumeração dos vértices em ordem decrescente de graus. [Pensando bem, "número de vizinhos" é mais relevante e mais apropriado que "grau".] A método seqüencial produz uma coloração ótima? E se os vértices estiverem em ordem crescente de graus?
[Importante] Suponha que nosso grafo não tem laços. Mostre que o método de coloração seqüencial, aplicado a qualquer enumeração dos vértices, usa no máximo Delta+1 cores, onde Delta é o grau de um vértice de grau máximo (Delta = maxv g(v)). É fácil mostrar algo melhor: que o número de cores não passa de Viz+1, onde Viz = maxv viz(v) e viz(v) é o número de vizinhos do vértice v.
[Bom] Suponha que meu grafo não tem laços e que cada componente do grafo tem um vértice com menos que Viz vizinhos, sendo Viz é o número máximo de vizinhos de um vértice. Escreva uma função C que produza uma coloração dos vértices do grafo com Viz ou menos cores. Sugestão: determine uma enumeração v[0], v[1], . . . , v[n–1] dos vértices tal que o número de vizinhos de v[i] em {v[0], v[1], . . . , v[i–1]} é estritamente menor que Viz; em seguida, faça uma coloração seqüencial.
[Ordenação por Grau Relativo] Suponha que a enumeração v[0], v[1], . . . , v[n–1] dos vértices de um grafo não-dirigido sem laços tenha a seguinte propriedade: para cada j, v[j] é um vértice com o menor número possível de vizinhos em {v[0], v[1], . . . , v[j–1]} é mínimo. Escreva uma função C que gere uma enumeração com essa propriedade e em seguinda faça uma coloração seqüencial. Essa heurística produz uma coloração ótima?
Gere a enumeração dos vértices aleatoriamente e depois aplique o método de coloração seqüencial.