O teorema das quatro cores explicado
Em 1852, um jovem matemático que coloria um mapa dos condados de Inglaterra reparou que quatro cores pareciam bastar para distinguir os condados vizinhos. Seria isso verdade para todos os mapas possíveis? A pergunta tornou-se um dos problemas mais famosos da matemática, atraiu uma célebre demonstração falsa que se manteve durante onze anos e foi finalmente resolvida em 1976 de uma forma que mudou aquilo que os matemáticos aceitam como demonstração.
A pergunta
Francis Guthrie, antigo aluno de Augustus De Morgan, perguntou se qualquer mapa pode ser colorido com quatro cores de modo que países que partilham uma fronteira recebam cores diferentes. Duas regras tornam a pergunta precisa. Os países têm de ser conexos, cada um numa só peça, e países que só se encontram num único ponto não contam como vizinhos. Três cores claramente nem sempre bastam, pois um país rodeado por um anel de outros três que se tocam todos precisa de uma quarta. A pergunta é se alguma vez é necessária uma quinta.
Mapas como grafos
Marque um ponto em cada país e trace uma linha entre dois pontos sempre que os respetivos países partilhem uma fronteira. O resultado é um grafo e, como o mapa está numa folha plana, as linhas podem ser traçadas sem se cruzarem: o grafo é planar. Colorir o mapa é colorir os vértices deste grafo de modo que as extremidades de cada aresta sejam diferentes. O menor número de cores que funciona é o número cromático, e o teorema das quatro cores afirma que nenhum grafo planar tem número cromático superior a quatro.
A demonstração falhada de Kempe
Em 1879, o advogado e matemático Alfred Kempe publicou uma demonstração. A sua ideia engenhosa, hoje chamada cadeias de Kempe, consiste em trocar duas cores ao longo de uma cadeia conexa de países para libertar uma cor onde ela é necessária. A demonstração foi aceite durante onze anos, até que Percy Heawood encontrou uma falha em 1890. A correção de Heawood demonstrou um resultado mais fraco: cinco cores bastam sempre. As cadeias de Kempe sobreviveram e tornaram-se uma ferramenta da demonstração final.
Porque é que cinco é fácil
Todo o grafo planar tem um vértice com no máximo cinco vizinhos; isto decorre da fórmula de Euler, que limita um grafo planar com n vértices a no máximo 3n − 6 arestas. Retire um desses vértices, pinte o resto do mapa pelo mesmo argumento e volte a colocar o vértice. Se os seus vizinhos usarem menos de cinco cores, uma está livre. Se usarem as cinco, uma troca ao longo de uma cadeia de Kempe liberta sempre uma. Com quatro cores, a mesma troca pode falhar, e é exatamente essa a falha que escapou a Kempe.
A demonstração por computador
Em 1976, Kenneth Appel e Wolfgang Haken, da Universidade do Illinois, demonstraram o teorema. Mostraram que todo o mapa contém pelo menos uma de 1936 configurações de um conjunto inevitável, e que cada configuração é redutível: um mapa mínimo que precisasse de cinco cores não a poderia conter. Verificar a redutibilidade exigiu mais de mil horas de computador, demasiado para verificar à mão. Muitos matemáticos sentiam-se pouco à vontade com uma demonstração que nenhuma pessoa conseguia ler por inteiro, e começou o debate sobre as demonstrações assistidas por computador.
Demonstrações mais simples e verificação completa
Em 1996, Neil Robertson, Daniel Sanders, Paul Seymour e Robin Thomas publicaram uma demonstração mais sistemática com 633 configurações, ainda verificada por computador mas mais fácil de confirmar. Em 2005, Georges Gonthier e Benjamin Werner formalizaram a demonstração inteira no assistente de demonstração Coq, de modo que um programa pequeno e de confiança verifica cada passo lógico. Hoje, o teorema das quatro cores é um dos resultados mais minuciosamente verificados da matemática.
Algoritmos de coloração
Encontrar uma coloração com quatro cores de um dado mapa é rápido na prática, mas encontrar o menor número de cores para um grafo qualquer é difícil: decidir se três cores bastam é NP-completo. Entre os métodos práticos estão a coloração gulosa por ordem decrescente de grau, o DSATUR, que colore a seguir o vértice mais restrito, e a pesquisa com retrocesso, que explora escolhas e as desfaz quando fica bloqueada. A coloração de grafos serve para marcar exames sem sobreposições, atribuir frequências de rádio de modo que emissores vizinhos não interfiram e alocar registos em compiladores.
Explore
Abra o pintor de mapas das quatro cores para gerar mapas de 4 a 120 países, pintá-los à mão com quatro cores e ver os conflitos aparecerem a vermelho. Deixe a coloração gulosa, o DSATUR ou o retrocesso resolver o mapa passo a passo, mostre o grafo dos países vizinhos e verifique o número mínimo de cores de que o mapa realmente precisa.
Perguntas frequentes
O teorema ajuda os cartógrafos?
Pouco. Os mapas reais costumam ser coloridos com mais cores para maior clareza, e incluem oceanos, lagos e países em várias partes, que o teorema não abrange. A sua importância é matemática: impulsionou o desenvolvimento da teoria dos grafos e levantou a questão do que conta como demonstração.
O que é uma cadeia de Kempe?
Tome duas cores, digamos vermelho e azul, e um país colorido de vermelho. A sua cadeia de Kempe é o conjunto de todos os países vermelhos e azuis que se conseguem alcançar a partir dele passando apenas por vizinhos vermelhos e azuis. Trocar vermelho e azul em toda a cadeia mantém a coloração válida e pode libertar uma cor para um país junto à cadeia.
Porque é que países em várias partes invalidam o teorema?
Se um país puder ser formado por regiões separadas que tenham todas de ter a mesma cor, o grafo de vizinhança deixa de ser planar, e podem construir-se mapas que precisam de qualquer número de cores até 12 com duas partes por país, como Heawood estudou no seu problema dos impérios.
Porque é que o pintor cria mapas a partir de pontos?
Cada país é a região do quadrado mais próxima de um ponto aleatório do que de qualquer outro, um diagrama de Voronoi. Isto dá mapas de aspeto realista com países convexos, e dois países são vizinhos exatamente quando as suas regiões partilham um troço de fronteira, o que a aplicação calcula com precisão.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Abrir o pintor de mapas das quatro cores