Coloração de Grafos

Colorir um grafo é atribuir rótulos aos vértices de forma que vértices adjacentes recebam rótulos distintos. É a formulação abstrata de todo problema de alocação sob conflito: dois recursos que não podem coexistir viram vértices adjacentes.

Definições

Uma coloração própria com $k$ cores é uma função $c: V \to {1,\dots,k}$ tal que $c(u) \ne c(v)$ para toda aresta ${u,v}$.

O número cromático $\chi(G)$ é o menor $k$ para o qual existe coloração própria.

Determinar $\chi(G)$ é NP-difícil; até decidir se $\chi(G) \le 3$ é NP-completo. Na prática usam-se heurísticas e limites.

Limites

$$\chi(G) \le \Delta(G) + 1$$

com $\Delta(G)$ o grau máximo. A prova é o próprio algoritmo guloso: ao colorir um vértice, seus vizinhos ocupam no máximo $\Delta$ cores, então sempre sobra uma.

O teorema de Brooks refina: para grafo conexo que não seja completo nem ciclo ímpar, $\chi(G) \le \Delta(G)$.

Por baixo, $\chi(G) \ge \omega(G)$, o tamanho da maior clique — um conjunto de vértices mutuamente adjacentes precisa de uma cor cada.

Casos especiais

Grafo	$\chi$
Completo $K_n$	$n$
Bipartido (com aresta)	$2$
Ciclo par	$2$
Ciclo ímpar	$3$
Árvore (com aresta)	$2$
Planar	$\le 4$

$\chi(G) \le 2$ equivale a ser bipartido, o que se testa em tempo linear com BFS de duas cores. A partir de 3 cores o problema já é NP-completo — um salto de dificuldade abrupto.

O teorema das quatro cores (Appel e Haken, 1976) afirma que todo grafo planar é 4-colorível. Foi o primeiro teorema importante cuja prova dependeu essencialmente de verificação por computador, o que gerou um debate duradouro sobre o que conta como demonstração matemática.

Algoritmo guloso

def coloracao_gulosa(grafo, ordem):
    cor = {}
    for v in ordem:
        usadas = {cor[u] for u in grafo[v] if u in cor}
        c = 0
        while c in usadas:
            c += 1
        cor[v] = c
    return cor

O guloso usa no máximo $\Delta + 1$ cores, mas o resultado depende fortemente da ordem. Existe sempre uma ordem que produz a coloração ótima — e encontrá-la é o problema difícil.

Heurísticas de ordenação que funcionam bem:

• Welsh-Powell: por grau decrescente. Trata primeiro os vértices mais restritos.
• DSATUR: a cada passo escolhe o vértice com maior número de cores distintas na vizinhança. Costuma dar resultados bem melhores e é ótima em grafos bipartidos.
• Ordem de eliminação perfeita: em grafos cordais, produz o ótimo.

Alocação de registradores

Esta é a aplicação canônica em compiladores, e vale entender em detalhe.

Cada variável do programa vira um vértice. Duas variáveis são adjacentes quando estão vivas ao mesmo tempo — o que forma o grafo de interferência. As cores são os registradores da máquina.

Se $\chi(G) \le k$, com $k$ o número de registradores, todas as variáveis cabem em registradores. Caso contrário, alguma precisa ir para memória — o spill, cuja escolha o compilador faz por heurística de custo.

O algoritmo clássico de Chaitin remove repetidamente vértices de grau menor que $k$ (que sempre poderão ser coloridos depois), empilhando-os; se travar, escolhe um candidato a spill. A coloração é feita ao desempilhar.

É uma tradução perfeita: um problema aparentemente de engenharia é exatamente um problema de teoria dos grafos, e usar a teoria dá tanto o algoritmo quanto o limite de qualidade.

Outras aplicações

Escalonamento de provas. Disciplinas com alunos em comum viram vértices adjacentes; as cores são horários. O número cromático é a menor quantidade de horários necessária.

Alocação de frequências. Antenas próximas interferem; frequências são cores. É o problema original que motivou boa parte da teoria.

Sudoku. Um sudoku é uma coloração de grafo com 9 cores, em que células da mesma linha, coluna ou bloco são adjacentes.

Paralelismo. Tarefas que disputam o mesmo recurso não podem rodar juntas; cores são fatias de tempo.

Compilação de consultas. Alocação de buffers em planos de execução usa a mesma modelagem.

Exemplo trabalhado

Considere o ciclo $C_5$ (cinco vértices em círculo). Como é ciclo ímpar, $\chi(C_5) = 3$. Tentando com duas cores, a alternância percorre o ciclo e o quinto vértice acaba adjacente a dois vértices que já ocupam as duas cores. O grau máximo é $2$, e o teorema de Brooks não se aplica justamente porque ciclos ímpares são a exceção — coerente com $\chi = 3 = \Delta + 1$.

Erros comuns

• Supor que o guloso dá o ótimo. Ele dá um limite superior, e a qualidade depende da ordem.
• Confundir $\chi(G)$ com $\Delta(G)$. O grau máximo é limite, não valor.
• Achar que 2 cores é fácil e 3 é só um pouco mais difícil. A fronteira entre P e NP-completo está exatamente aí.
• Ignorar a estrutura do grafo. Grafos cordais, de intervalo e planares têm algoritmos eficientes que não valem no caso geral.

Leituras recomendadas

• Diestel, capítulo 5 — coloração com as provas dos teoremas de Brooks e Vizing.
• Documentação do LLVM sobre alocação de registradores — a teoria aplicada num compilador de produção.
• Garey e Johnson — a referência sobre NP-completude, com a prova para 3-coloração.
• West, capítulo 5 — muitos exercícios de coloração.

Reinhard Diestel (2017). Graph Theory. Springer. DOI: 10.1007/978-3-662-53622-3. Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 9780716710448. Douglas B. West (2001). Introduction to Graph Theory. Prentice Hall. Página oficial.

Referências

1. Reinhard Diestel (2017). Graph Theory. Springer.
2. Michael R. Garey; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
3. Douglas B. West (2001). Introduction to Graph Theory. Prentice Hall.