Coloração de grafos
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.
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
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.
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 kn 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.445n).
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. 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).
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: O algoritmo apresentado tem complexidade O(n2).==Referências==
