English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGrafos e RedesColoração de Mapa
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
South America
Germany
England
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
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
Pouco progresso foi feito no problema das quatro cores até 1976, quando
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.