Diário das pequenas descobertas da vida.
Sexta-feira, 11 de Novembro de 2005
Quatuor colores
Corria o ano de 1852. Francis Guthrie entretinha-se a pintar um mapa dos condados da Inglaterra.
Conseguiu pintar todos os condados com apenas 4 cores, não tendo condados com fronteiras comuns a mesma cor (excepto quando a fronteira é apenas um ponto).

Tentou então pintar outro mapa dos condados, mas desta vez com apenas 3 cores. Mas por muito que tentasse não conseguia pintá-los sem que dois condados adjacentes tivessem sempre cores diferentes.

Continuou a tentar e continuou a não conseguir.
Tentou com outros mapas mais simples e conseguia pintá-los com menos cores.
Mas outros mapas que tentava colorir só conseguia com 4 cores.
Todos os mapas que coloria precisavam sempre no máximo de 4 cores para serem pintados sem que regiões com fronteiras comuns (excepto pontos) tivessem a mesma cor.

Conjecturou então que, se calhar, todos os mapas podiam ser pintados com no máximo 4 cores. Era uma conjectura interessante porque era simples, fácil de enunciar e de perceber, de aplicação universal e com aplicações práticas importantes.
Mas era uma conjectura. Não estava provada. Não haveria algum mapa, por muito que estranho que fosse, que tivesse de ser colorido com mais de 4 cores?

Apesar de ser um Matemático, Guthrie não conseguiu demonstrar a sua conjectura. Colocou então esta questão ao grande matemático De Morgan (que é um dos Matemáticos com um dos nomes mais engraçados para fazer jogos de palavras. «Meninos, de quem é este livro?» «De De Morgan!»). De Morgan é especialmente conhecido pelos seus resultados na Lógica (o facto de a negação de uma negação ser uma afirmativa, de uma implicação ser equivalente a uma negação disjunta com uma afirmação,...)

Entretanto algumas «demonstrações» iam surgindo, mas todas acabaram por se revelar falaciosas. Uma delas, feita pelo Matemático Kempe, em 1879, foi aceite durante uma década, até que outro Matemático de nome Heawood encontrou um mapa, com 18 cores, no qual o resultado de Kempe falhava.

O resultado ficou por demonstrar até que, em 1977, dois Matemáticos (Appel e Haken) fizeram um programa de computador, que correram num super-computador, que permitiria demonstrá-lo. Reduziram então todos os mapas a um conjunto de mapas-padrão (mapas modulares). Qualquer mapa pode ser transformado num de 1482 configurações modulares de mapas. O computador verificou que todas elas se poderiam colorir com 4 cores, provando assim que qualquer mapa também o poderia. A muitos matemáticos esta demonstração era ligeiramente frustrante, pois baseou-se no cálculo bruto, em cálculos que ninguém poderia verificar manualmente, fazendo os mesmos cálculos e procurar erros. Apesar de a confiança nos computadores ser grande, é difícil confiar no que não se vê. A demonstração não foi aceite por todos, aguardando muitos uma demonstração mais «clássica».

Em Dezembro de 2004, numa conferência científica na França, o Matemático Gonthier (juntamente com Werner) reformularam a prova, podendo dessa forma validar todos os passos dos cálculos computacionais.
O teorema das 4 Cores estava finalmente provado.
Qualquer mapa pode ser colorido com 4 ou menos cores (pode-se sempre usar mais, mas este é o mínimo necessário).

Mas há uma forma simples de encontrar o número de cores necessário para colorir uma mapa que tem aplicações para encontrar o número mínimo de grupos necessários para realizar uma dada tarefa.
Essa forma simples envolve o uso de grafos
(de que se falou no artigo As pontes de Königsberg).

Um grafo é uma forma de esquematizar ligações entre itens, de forma a facilitar o encontro das formas mais eficazes de realizar tarefas entre esses itens.
Um grafo é assim um simples conjunto de pontos (vértices) ligados por linhas (arestas) que representam a ligação entre os pontos.
No caso das pontes de Königsberg, cada aresta representava uma ponte. Procurou-se assim uma forma percorrer todas as pontes uma só vez e regressar à de origem (Euler mostrou que era impossível).

Como usar então os grafos para encontrar o mínimo número de grupos que se podem formar para realizar uma dada tarefa, respeitando as limitações impostas?
Atente-se no seguinte exemplo:
«Um jornal é constituido por 6 secções. A Sofia trabalha nas notícias e na economia, o Bernardo nas notícias e no desporto, a Luísa na gastronomia e na moda, o João no moda e na economia, a Eduarda na gastronomia e no desporto, o Miguel na economia e na moda, a Carla nas notícias e na política. Pretende-se fazer reuniões com as pessoas que trabalham nas secções para planear a próxima edição. Como nenhum pode estar em duas reuniões simultaneamente, qual é o número mínimo de horas necessário para fazer as reuniões?»
Comece-se por esquematizar a situação com um grafo. Cada vértice é uma secção, cada aresta representa a impossibilidade da realização das tarefas simultaneamente (por terem as mesmas pessoas nelas a trabalhar).

A Sofia trabalha nas notícias e na economia. Como o Bernardo também trabalha nas notícias, as duas reuniões (notícias e economia) têm de se fazer a horas diferentes. Ligam-se então os vértices N(otícias) com o vértice E(conomia). Da mesma forma, como a Luísa trabalha no desporto e na gastronomia, as duas têm de se fazer a horas diferentes. Assim D e G são unidas por uma aresta (que representa impossibilidade de realização simultânea).

Poderia parecer que seriam precisas tantas horas quanto o número de reuniões, uma hora para cada. Mas não é bem assim. Há reuniões que, não tendo pessoas em comum, se podem realizar as mesmo tempo (em salas diferentes). Basta então analizar o grafo e verificar que:

As N(otícias) e a G(astronomia) podem-se realizar ao mesmo tempo (como não têm arestas entre elas não têm pessoas em comum). Ficam então representadas com a mesma cor. Mas, apesar de N se puder realizar com M(oda), G e M não podem. Assim M fica com uma cor diferente. M pode ser realizada com P(olítica). Ficam da mesma cor. Mas D(esporto) não pode ser feito à mesma hora (por causa de P). Então D fica com outra cor. D pode ser realizada com E(conomia), por isso ficam da mesma cor. Estão então todas as secções escolhidas, havendo 3 cores no total (diz-se que o número cromático é 3). Este é o número mínimo de horas necessárias para fazer todas as reuniões.
Podem ser feitas a de notícias e gastronomia ao mesmo tempo; política e moda ao mesmo tempo; desporto e economia ao mesmo tempo.

O número cromático é sempre o menor número de arranjos que se podem fazer. Mesmo que se encontre outros arranjos
(por exemplo, podia ser
gastronomia, economia e política ao mesmo tempo;
notícias e moda;
desporto)
o número mínimo será sempre de 3 nesta questão.


Este método da coloração de grafos pode também ser usada para determinar o número mínimo de cores que se pode usar para pintar um mapa sem que regiões vizinhas fiquem com a mesma cor.
Suponhamos o seguinte mapa:

Neste exemplo muito simples, era fácil de saber que bastavam 3 cores. Mas se se representar cada região por um vértice e cada fronteira comum com um vértice, depois colorir os vértices que não se ligam directamente, também se contata que se usa 3 cores.
O número cromático é 3, pelo que o número mínimo de cores necessária é 3.

Mas imaginemos que era uma mapa de Portugal. Seria mais complicado de representar com um grafo e mais ainda verificar a olho quantas cores seriam necessárias. No máximo serão 4. Mas será que se poderiam usar menos?
Tem de se fazer o grafo e determinar o número cromático.

Constata-se que é 3. São necessárias no mínimo 3 cores para pintar Portugal.

Ao contrário da crença popular, que insiste em pintar o Mundo com as cores futebolísticas, o mundo pode ser pintado com no mínimo com 4 cores.
Se bem que, numa estranha analogia com a obcessão nacional com o futebol, Portugal é mesmo colorido com no mínimo 3 cores, que podem ser o vermelho, o verde e o azul.
Mas pode (e deve), em sentido social, ser pintado com as 7 do arco-íris...

Aqui está o artigo sobre a coloração de mapas usando grafos referida por «.» num comentário anterior.
No título «A quatro cores»


Respondendo ao apelo deixado por «elf», aqui estão exemplos de grafos que se pintam com um número de cores diferente de 3. Mas o máximo é mesmo sempre 4...


Publicado por Mauro Maia às 19:53
Atalho para o Artigo | Adicionar aos favoritos

De Lady Nox a 13 de Novembro de 2005 às 23:58
Há quanto tempo não ouvia falar de grafos! Acho que a primeira vez foi quando li "O Homem que só gostava de números", sobre o Paul Erdös. Livro fascinante... Como de costume, o artigo está óptimo :)


Comentar:
De
  (moderado)
Nome

Url

Email

Guardar Dados?

Este Blog tem comentários moderados

(moderado)
Ainda não tem um Blog no SAPO? Crie já um. É grátis.

Comentário

Máximo de 4300 caracteres


Copiar caracteres

 



O dono deste Blog optou por gravar os IPs de quem comenta os seus posts.

Cognosco ergo sum

Conheço logo sou

no Cognosco
 
Cogitações recentes
Pergunta feita por um menino de 14 anos... Mas a p...
Essa pergunta é interessante: será que ele se quei...
O fogo é fruto de uma reação química, não tem esta...
Olá Ribeiro. Eis um link atualizado para a folha d...
Seria possível fornecer um link atualizado para o ...
Artigos mais cogitados
282 comentários
74 comentários
66 comentários
62 comentários
44 comentários
Artigos

Setembro 2018

Novembro 2017

Outubro 2017

Agosto 2017

Julho 2017

Junho 2017

Maio 2017

Abril 2017

Março 2017

Fevereiro 2017

Janeiro 2017

Dezembro 2016

Novembro 2016

Outubro 2016

Julho 2016

Março 2015

Dezembro 2014

Outubro 2013

Maio 2013

Fevereiro 2013

Outubro 2012

Setembro 2012

Agosto 2012

Junho 2012

Janeiro 2012

Setembro 2011

Abril 2011

Fevereiro 2011

Dezembro 2010

Maio 2010

Janeiro 2010

Abril 2009

Fevereiro 2009

Janeiro 2009

Novembro 2008

Outubro 2008

Agosto 2008

Julho 2008

Junho 2008

Abril 2008

Fevereiro 2008

Janeiro 2008

Novembro 2007

Outubro 2007

Agosto 2007

Julho 2007

Junho 2007

Maio 2007

Abril 2007

Março 2007

Fevereiro 2007

Janeiro 2007

Dezembro 2006

Novembro 2006

Outubro 2006

Setembro 2006

Agosto 2006

Julho 2006

Junho 2006

Maio 2006

Abril 2006

Março 2006

Fevereiro 2006

Janeiro 2006

Dezembro 2005

Novembro 2005

Outubro 2005

Setembro 2005

Julho 2005

Junho 2005

Maio 2005

Abril 2005

Março 2005

Fevereiro 2005