Países
Fronteiras
Cores usadas
Conflitos

Mais sobre o teorema das quatro cores

Pintor de mapas do teorema das quatro cores

Por mais complicado que um mapa seja, quatro cores bastam sempre para o colorir de modo que países que partilham uma fronteira nunca tenham a mesma cor. O enunciado é tão simples que uma criança o pode testar com lápis de cor, e no entanto foram precisos mais de um século e um computador para o demonstrar. Pinte um mapa aleatório, veja que fronteiras estão em conflito e depois observe três métodos a fazê-lo, desde uma regra gulosa rápida que por vezes precisa de uma quinta cor até uma pesquisa com retrocesso que se arranja sempre com quatro. Escolha uma cor e clique nos países para os pintar; uma fronteira fica vermelha quando dois vizinhos têm a mesma cor. Países que só se tocam num canto podem ter a mesma cor. Ou deixe o computador fazê-lo: escolha um método e prima Resolver para o ver trabalhar, ou Passo para acompanhar um movimento de cada vez. Mínimo de cores verifica se este mapa poderia ficar com três cores, ou até com duas. Novo mapa desenha outro mapa, e Mostrar os vizinhos desenha a rede de países que partilham uma fronteira.

Como funciona

  1. Escolha o número de países e prima Novo mapa, ou comece com o mapa apresentado.
  2. Escolha uma cor e clique nos países para os pintar, atento às fronteiras vermelhas onde os vizinhos entram em conflito.
  3. Escolha um método e prima Resolver ou Passo para o ver colorir o mapa, e prima Mínimo de cores para ver de quantas cores este mapa precisa.

Dos mapas aos grafos

Coloque um ponto em cada país e ligue dois pontos quando os respetivos países partilham uma fronteira. O mapa torna-se um grafo, e colorir o mapa é o mesmo que colorir os pontos de modo que pontos ligados sejam diferentes. Como os mapas são desenhados numa folha plana, estes grafos são planares: podem ser desenhados sem linhas que se cruzem. Países que se encontram num único ponto, como quatro quadrados num canto, não são vizinhos. O teorema das quatro cores diz que todo o grafo planar pode ser colorido com quatro cores. Ative Mostrar os vizinhos para ver o grafo do mapa atual.

Três formas de colorir

A coloração gulosa pega nos países um de cada vez, primeiro os que têm mais vizinhos, e dá a cada um a primeira cor que os seus vizinhos não usaram. É rápida mas míope, e em alguns mapas recorre a uma quinta ou até a uma sexta cor. O DSATUR, inventado por Daniel Brélaz em 1979, escolhe sempre a seguir o país cujos vizinhos já mostram mais cores diferentes, o que normalmente evita essa armadilha. O retrocesso experimenta as cores à vez e, quando um país fica sem nenhuma, desfaz as escolhas mais recentes e tenta de novo; encontra sempre uma coloração com quatro cores, por vezes depois de recuar muitas vezes.

Perguntas frequentes

Porque é que quatro cores bastam sempre?

Ninguém encontrou uma razão curta. A demonstração de Kenneth Appel e Wolfgang Haken, em 1976, mostrou que todo o mapa tem de conter uma de 1936 pequenas configurações e que cada uma delas pode ser removida e a coloração restaurada depois; verificá-las todas exigiu mais de mil horas de tempo de computador. Uma demonstração por computador mais simples de Neil Robertson, Daniel Sanders, Paul Seymour e Robin Thomas, em 1996, precisa de 633 configurações, e em 2005 Georges Gonthier verificou uma demonstração por completo com o assistente de demonstração Coq.

Há mapas que precisam das quatro cores?

Sim. Quatro países que tocam cada um os outros três, como um país rodeado por um anel de outros três, precisam de quatro. Muitos mapas, porém, arranjam-se com três, e Mínimo de cores descobre-o para o mapa no ecrã. Decidir em geral se um mapa pode ser colorido com três cores é um problema difícil, NP-completo, apesar de quatro cores bastarem sempre.

Porque é que o método guloso usa por vezes cinco cores?

Colore cada país uma única vez e nunca muda de ideias. Uma escolha inicial pode deixar um país posterior rodeado pelas quatro cores, e a única saída é uma quinta. O retrocesso, em vez disso, voltaria atrás e alteraria as escolhas anteriores.

O teorema é válido noutras superfícies?

Numa esfera, sim: é o mesmo que o plano. Num toro, a superfície de um donut, alguns mapas precisam de sete cores, e sete bastam sempre, como mostrou Percy Heawood. Se os países puderem ser formados por várias partes separadas, como uma nação com colónias, quatro cores deixam de bastar.

É enviado algo para um servidor?

Não. O mapa, os métodos de coloração e a verificação são executados no seu navegador. As suas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor