Glossário

Selecione uma das palavras-chave à esquerda…

Grafos e RedesColoração de Mapa

Tempo de leitura: ~15 min

Já usamos a teoria dos grafos em certos mapas. À medida que diminuímos o zoom, estradas e pontes individuais desaparecem e, em vez disso, vemos o contorno de países inteiros. Ao colorir um mapa - ou qualquer outro desenho que consiste em regiões distintas - os países adjacentes não podem ter a mesma cor. Também podemos usar o mínimo de cores possível. Alguns "mapas" simples, como um tabuleiro de xadrez, precisam apenas de duas cores (preto e branco), mas os mapas mais complexos precisam de mais.

Ao colorir o mapa dos estados dos EUA, 50 cores são obviamente suficientes, mas são necessárias muito menos. Tente colorir os mapas abaixo com o mínimo de cores possível:

United States

Number of colours: 0

South America

Number of colours: 0

Germany

Number of colours: 0

England

Number of colours: 0

Todos esses mapas podem ser coloridos com apenas quatro cores diferentes, mas não é difícil imaginar que outros mapas muito complicados pode precisar de muito mais cores. De fato, alguns mapas precisam de pelo menos quatro cores, sempre que contenham quatro países, todos conectados um ao outro.

Como antes, podemos converter um mapa com países e fronteiras em um gráfico planar: todo país se torna e países que conecte-se por uma aresta:

Agora, queremos colorir os vértices de um gráfico, e dois vértices devem ter uma cor diferente se estiverem conectados por uma aresta.

Em 1852, o estudante de botânica Francis Guthrie teve que colorir um mapa dos condados da Inglaterra. Ele observou que quatro cores pareciam suficientes para qualquer mapa que ele tentasse, mas ele não conseguiu encontrar uma prova que funcionasse para todos os mapas. Esse acabou sendo um problema extremamente difícil e ficou conhecido como o teorema das quatro cores. Durante os 100 anos seguintes, muitos matemáticos publicaram "provas" para o teorema das quatro cores, apenas para erros encontrados posteriormente. Algumas dessas provas inválidas foram tão convincentes que levou mais de 10 anos para descobrir erros. Durante muito tempo, os matemáticos foram incapazes de provar que quatro cores são suficientes ou de encontrar um mapa que precisava de mais de quatro cores.

Pouco progresso foi feito no problema das quatro cores até 1976, quando Wolfgang Haken e Kenneth Appel usaram um computador para finalmente resolvê-lo. Eles reduziram infinitamente muitos mapas possíveis para 1936 casos especiais, cada um verificado por um computador, levando mais de 1000 horas no total.

O teorema das quatro cores é o primeiro teorema matemático conhecido a ser provado usando um computador, algo que se tornou muito mais comum e menos controverso desde então. Computadores mais rápidos e um algoritmo mais eficiente significam que hoje você pode resolver o teorema das quatro cores em um laptop em apenas algumas horas.

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

O teorema das quatro cores funciona apenas para mapas em um plano ou esfera, e onde todos os países consistem em uma única área.

No entanto, os matemáticos também analisaram mapas de impérios, onde os países podem consistir em múltiplos componentes desconectados e em mapas de planetas de formas diferentes, como um toro (forma de rosca). Nesses casos, você pode precisar de mais de quatro cores e as provas se tornam ainda mais difíceis.

This map on a torus requires seven colours.