Coloração de grafos: do mapa ao número cromático

Coloração de grafos

Um mapa de países ou regiões vira um grafo quando cada região é um vértice e duas regiões que dividem fronteira viram uma aresta. Pintar o mapa sem que regiões vizinhas tenham a mesma cor é o mesmo que colorir os vértices de modo próprio: vizinhos recebem cores diferentes.

O menor número de cores que faz isso é o número cromático, χ(G). O teorema das quatro cores diz que todo mapa plano pode ser pintado com 4 cores. A aula O problema das quatro cores trata dele; aqui o foco é o algoritmo sobre o grafo.

Coloração gulosa

A gulosa percorre os vértices em uma ordem fixa e dá a cada um a menor cor que nenhum vizinho já colorido usa. Ela é rápida e sempre produz uma coloração própria, mas o número de cores depende da ordem: uma ordem ruim pode gastar mais cores do que o necessário.

A ordem de Welsh-Powell coloca primeiro os vértices de maior grau, porque eles têm mais restrições. Ela costuma ajudar, mas não garante o ótimo.

Número cromático exato

Para grafos pequenos, o programa testa se é possível colorir com k − 1 cores, depois com k − 2, até falhar. A busca é por tentativa e erro com poda; por isso só é feita até 14 vértices, e o painel do editor só calcula ao vivo até 10. Em grafos maiores, o problema fica caro rapidamente.

Lições úteis

• Um triângulo (ou qualquer clique de k vértices) força pelo menos k cores.
• Um grafo bipartido tem número cromático 2, e um ciclo par também; um ciclo ímpar precisa de 3.
• Um laço torna impossível a coloração própria: o vértice seria vizinho de si mesmo.

Sobre o mapa desta aula

O grafo de exemplo com as cinco regiões do Brasil usa fronteiras simplificadas, só para ilustrar a construção. Ele não é um levantamento oficial de fronteiras entre estados.