59. Reuniões coloridas

   Corria o ano de 1852. Francis Guthrie entretinha-se a pintar um mapa dos condados (mais ou menos como os concelhos em Portugal) da Inglaterra. Conseguiu pintar todos os condados com apenas 4 cores, não tendo condados com fronteiras comuns a mesma cor (menos quando a fronteira era 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. 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 (excluindo pontos) tivessem a mesma cor. Conjeturou então que todos os mapas podiam ser pintados com, no máximo, 4 cores. Era uma hipótese 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 conjetura. 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 hipótese. Colocou então esta questão ao grande matemático 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 Alfred Bray Kempe, em 1879, foi aceite durante uma década, até que outro Matemático de nome Percy John 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 numa de 1936 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 testar e analisar. A demonstração não foi aceite por todos, aguardando muitos uma demonstração mais «clássica». 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 Pontes e grafos. Um grafo é uma forma de esquematizar ligações entre itens, de forma a permitir encontrar 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).

 Atente-se no seguinte exemplo: «Um jornal é constituído por 6 secções. A Sofia faz as notícias e a economia, o Bernardo as notícias e o desporto, a Luísa a gastronomia e a moda, o João a moda e a economia, a Eduarda a gastronomia e o desporto, o Miguel a economia e a moda, a Carla as notícias e a 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. Há reuniões que, não tendo pessoas em comum, se podem realizar as mesmo tempo (em salas diferentes). Basta então analisar o grafo e verificar que as N(otícias) e a G(astronomia) se podem 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 diretamente, também se verifica 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. Portugal pode ser 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…

   Eis exemplos de grafos que se pintam com um número de cores diferente de 4. Mas o máximo necessário é mesmo sempre 4… 

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *