Coloração de vértices de grafos

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 a 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 1

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.

Cobertura por conjuntos estáveis

Uma cobertura por conjuntos estáveis é uma coleção E₁, E₂, … , E_k de conjuntos estáveis tal que cada vértice do grafo pertence a algum E_i, ou seja, tal que a união de E₁, E₂, … , E_k seja o conjunto de todos os vértices do grafo. (A definição permite que um vértice pertença a dois ou mais conjuntos estáveis diferentes, ou seja, tenha duas ou mais cores diferentes. Mas isso não é importante: se E_i intersecta E_j, basta trocar E_i por E_i − E_j e observar que esse último conjunto também é estável.)

Uma cobertura por conjuntos estáveis é o mesmo que uma coloração de vértices: cada E_i corresponde a uma cor. 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 2

Suponha que cada vértice v de um grafo não-dirigido tem uma cor vcor (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.
Suponha que E₁, E₂, … , E_k é uma cobertura de um grafo não-dirigido por conjuntos estáveis. É verdade que cada E_i é um conjunto estável máximo? É verdade que cada E_i é 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++) vcor = 1;
k = 0;
do {
flag = 0;
k++;
for (v = v0; v < vn; v++) {
if (vcor ≠ k) continue;
for (a = varcs; a ≠ NULL; a = anext) {
if (atipcor ≡ k) {
atipcor = k+1;
flag = 1; } } }
} while (flag ≡ 1);

Heurísticas

Não conheço 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, métodos 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 sequencial dos vértices. Suponha dada uma enumeração dos vértices do grafo, ou seja, uma sequê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 gvertices da estrutura de dados do SGB.) Para encontrar uma coloração dos vértices a partir dessa enumeração basta fazer o seguinte (supondo que o grafo não tem laços):

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 3-10, temos cores 1, … , k e os vértices v[0], v[1], … , v[ j−1] já estão coloridos. O bloco de linhas 4-10 atribui a menor cor possível a v[ j].

Exercícios 3

Implemente uma versão do método de coloração sequencial de vértices. Use a ordem em que os vértices aparecem no vetor gvertices 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 sequencial de vértices. A enumeração dos vértices que servirá de base para a coloração é v, vprox, vproxprox, 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 sequencial 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 sequencial, aplicado a qualquer enumeração dos vértices, usa no máximo Delta + 1 cores, sendo Delta o grau de um vértice de grau máximo (Delta = max_v g(v)). É fácil mostrar algo melhor: que o número de cores não passa de Viz + 1, onde Viz = max_v 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: Encontre 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] seja estritamente menor que Viz. Em seguida, faça uma coloração sequencial.)
[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 sequencial. 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 sequencial.