Cognosco

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...