Coloração de grafos

Uma coloração adequada de vértices para o grafo de Petersen com 3 cores, o número mínimo possível.

Em teoria dos grafos, coloração de grafos é um caso especial de rotulagem de grafos; é uma atribuição de rótulos tradicionalmente chamados "cores" a elementos de um grafo sujeita a certas restrições. Em sua forma mais simples, é uma forma de colorir os vértices de um grafo tal que não haja dois vértices adjacentes que compartilhem a mesma cor; isso é chamado de uma coloração de vértices. Da mesma forma, uma coloração de arestas atribui uma cor para cada aresta de modo que não haja duas arestas adjacentes da mesma cor, e uma coloração de faces de um grafo planar atribui uma cor para cada face ou região de modo que não haja duas faces que compartilham uma fronteira tendo a mesma cor.

A coloração de vértices é o ponto de partida para o assunto, e outros problemas de coloração podem ser transformados em uma versão de vértices. Por exemplo, uma coloração de arestas de um grafo é simplesmente uma coloração de vértices do seu grafo linha, e uma coloração de face de um grafo planar é apenas uma coloração de vértices do seu dual planar. No entanto, problemas de coloração de não-vértices são muitas vezes referidos e estudado como são. Isso se deve em parte à perspectiva, e em parte porque alguns problemas são mais bem estudados na forma não-vértice, como por exemplo, a coloração de arestas.

A convenção do uso de cores provém de colorir os países de um mapa, onde cada face é literalmente colorida. Este foi generalizado para coloração das faces de um grafo incorporado no plano. Pela dualidade planar se passou a colorir os vértices, e desta forma se generalizou a todos os grafos. Em representações matemáticas e na informática é comum usar os primeiros números inteiros positivos ou não negativos como as "cores". Em geral pode-se usar qualquer conjunto finito como "conjunto de cores". A natureza do problema de coloração depende do número de cores, mas não sobre o que são.

A coloração de grafos goza de muitas aplicações práticas, bem como desafios teóricos. Ao lado dos tipos clássicos de problemas, limitações diferentes também podem ser definidas no grafo, ou na forma como uma cor é atribuída, ou mesmo sobre a própria cor. Ela chegou até a se popularizar com o público em geral na forma da popular série de quebra-cabeças Sudoku. A coloração de grafos ainda é um campo de pesquisa muito ativa.

História

Os primeiros resultados sobre coloração de grafos lidam quase que exclusivamente com grafos planares na forma da coloração de mapas. Enquanto tentava colorir um mapa dos condados da Inglaterra, Francis Guthrie postulou a conjectura das quatro cores, notando que quatro cores eram suficientes para colorir o mapa, para que as regiões que partilham uma fronteira comum não recebessem uma mesma cor. O irmão de Guthrie passou a pergunta para seu professor de matemática Augustus de Morgan da University College, que o mencionou a William Hamilton em 1852. Arthur Cayley levantou o problema em uma reunião do London Mathematical Society em 1879. No mesmo ano, Alfred Kempe publicou um artigo que afirmava ter estabelecido o resultado, e por uma década o problema das quatro cores foi considerado resolvido. Para sua realização Kempe foi eleito membro da Royal Society e mais tarde Presidente da Sociedade Matemática de Londres

Em 1890, Heawood apontou que o argumento de Kempe estava errado. No entanto, ele provou o teorema de cinco cores, dizendo que cada mapa planar pode ser colorido com não mais de cinco cores, usando idéias de Kempe. No século seguinte, uma grande quantidade de trabalhos e teorias foram desenvolvidas para reduzir o número de cores a quatro, até que o teorema de quatro cores foi finalmente provada em 1976 por Kenneth Appel e Wolfgang Haken. A prova voltou para as idéias de Heawood e Kempe e negligenciados os desenvolvimentos intervenientes.

A prova do teorema de quatro cores também é notável por ser a primeira grande prova auxiliada por computador.

A coloração de grafos tem sido estudada como um problema algorítmico desde o início da década de 1970: o problema número cromático é um dos 21 problemas NP-completos de Karp, de 1972. Vários algoritmos de tempo exponencial foram desenvolvidos com base no método de Zykov (1949).

Uma das principais aplicações de coloração de grafos, alocação de registradores em compiladores foi introduzida em 1981.

Definição e terminologia

Coloração de vértices

Seja G(V, E) um grafo, onde V é o conjunto de vértices e E o conjunto de arestas. Uma coloração para o grafo G é uma atribuição de cores para cada vértice de forma que vértices adjacentes tenham diferentes cores. De modo formal uma coloração consiste em função c:V(G) -> N tal que c(u) ≠ c(v), se u e v são vértices adjacentes.

Embora as cores usadas na representação do problema possam ser elementos de qualquer conjunto, cores reais (tais como verde, vermelho, azul e amarelo) somente são utilizadas quando um pequeno número de cores está sendo considerado. Em muitas situações inteiros positivos (1,2, ... , ݇k) são empregados para representar as cores.

O grafo G é k-colorível se podemos atribuir uma das k cores para colorir G.

O número cromático χ(G) de um grafo G é o menor número de cores necessárias para colorir G.

O problema das 4 cores refere-se apenas a grafos planares, ou seja, aquele nas quais os vértice podem ser dispostos no plano e é possível traçar todas as arestas sem cruzamentos entre as mesmas.

Não existe nenhum algoritmo eficiente que seja capaz de encontrar o número cromático ótimo de um grafo. O problema é NP-Completo.

Algoritmos

Uma vez que o problema da determinação do número cromático é classificado como NP-completo, qualquer algoritmo exato empregado em sua resolução terá complexidade exponencial, desta maneira, torna-se importante a utilização de técnicas heurísticas para solução aproximada desse problema em tempo polinomial.

Algoritmos exatos

A solução por força bruta para uma k-coloração deve considerar cada uma das kⁿ alocações de k cores para n vértices e verificar a viabilidade da solução. Tal abordagem é impraticável, exceto para grafos pequenos.

Usando programação dinâmica e um limite para o número de conjuntos independentes maximais, k-coloração pode ser decidido no tempo e no espaço em O(2.445ⁿ).

Algoritmo Welsh e Powell

Foi proposto por Welsh e Powell (1975). É um algoritmo guloso, visto que determina a cor do vértice ݆j após os ݆j-1 vértices terem sido coloridos, tendo sempre como propósito minimizar o número de cores necessárias.

Algoritmo WP(G=(V,E))
inicio
Ordenar os vértices {x1, x2, ..., xn} tq grau(xi) >= grau(xi+1)
para i<-2 até n faça  {inicilizar conjuntos de cores vazios}
   Ci <- {}
C1 <- {x1} {x1 recebe cor 1}
para i <- 2 até n faça
   k = Mínimo{j | Adj(xi) Inter Cj = {}, j=0, 1, ..., n
   ck = Ck U {xj}
fim-para
retornar Máximo{ j | Cj <> {}, j=1, 2, ..., n}
fim.

Análise de complexidade

A ordenação dos vértices em ordem não crescente de graus pode ser realizada em O(n.log n) com um algoritmo ótimo genérico. O cálculo do grau dos vértice é O(m + n), usando listas de adjacências.

A coloração propriamente depende da obtenção de até k cores, inserida em um laço O(n), implicando em custo O(k.n).

O custo global do algoritmo é O(n²).

Algoritmo DSATUR

É um método heurístico que apresenta um bom desempenho. É exato para grafos bipartidos e ferramenta importante para algoritmos que buscam cliques maximais em grafos.

Este algoritmo usa o conceito de grau de saturação de um vértice: grau de saturação de um vértice é o número de diferentes cores para o qual o mesmo é adjacente.

O algoritmo DSATUR, assim denominado em função do emprego do grau de saturação, pode ser então descrito como um procedimento que compreende a execução das seguintes etapas:

1. Ordene os vértices de G(V, E) em ordem decrescente de graus.
2. Atribua ao vértice de maior grau a cor 1.
3. Selecione o vértice com maior grau de saturação. Se houver vértices com mesmo grau de saturação, opte por qualquer um de grau máximo pertencente ao sub-grafo ainda não colorido.
4. Atribua ao vértice selecionado a cor de menor índice disponível.
5. Se todos os vértices estiverem coloridos, pare. Caso contrário, retorne à etapa 3.

O algoritmo apresentado tem complexidade O(n²).