Coloração de grafos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido. Ajude e colabore com a tradução.
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[editar | editar código-fonte]

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 Londres1 . Para sua realização Kempe foi eleito membro da Royal Society e, posteriormente, presidente da Sociedade de Matemática de Londres.2


Referências

  1. Kubale, M. (2004), Graph Colorings, American Mathematical Society, ISBN 0-8218-3458-4 
  2. M. Kubale, History of graph coloring, em Kubale (2004)