Saltar para o conteúdo

Teorema das quatro cores

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Problema das quatro cores)
Abstração de um mapa com 4 cores usando grafos
Mapa dos Estados Unidos desenhado com 4 cores; observe que até em estados que fazem fronteira com mais outros 3 estados não acabam coincidindo suas cores

Em matemática, o teorema das quatro cores, ou teorema do mapa das quatro cores, afirma que não mais do que quatro cores são necessárias para colorir as regiões de qualquer mapa, de modo que duas regiões adjacentes não tenham a mesma cor. Adjacente significa que duas regiões compartilham um segmento de curva limite comum, não apenas um canto onde três ou mais regiões se encontram.[1] Foi o primeiro teorema importante a ser provado usando um computador. Inicialmente, essa prova não foi aceita por todos os matemáticos porque a prova assistida por computador era inviável para um ser humano verificar manualmente.[2] Desde então, a prova ganhou ampla aceitação, embora alguns questionadores permaneçam.[3]

Diagrama com quatro cores

A sua formulação é a seguinte:

Dado um mapa plano, dividido em regiões, quatro cores são suficientes para colori-lo de forma a que regiões vizinhas não partilhem a mesma cor.

O teorema das quatro cores foi provado em 1976 por Kenneth Appel e Wolfgang Haken após muitas provas e contra-exemplos falsos (ao contrário do teorema das cinco cores, provado na década de 1800, que afirma que cinco cores são suficientes para colorir um mapa). Para dissipar quaisquer dúvidas remanescentes sobre a prova Appel-Haken, uma prova mais simples usando as mesmas ideias e ainda contando com computadores foi publicada em 1997 por Robertson, Sanders, Seymour e Thomas. Além disso, em 2005, o teorema foi provado por Georges Gonthier com software de prova de teorema de uso geral.[4][5]

Relação com outras áreas da matemática

[editar | editar código-fonte]

Dror Bar-Natan deu uma demonstração sobre Álgebra de Lie e Invariante de Vassiliev que é equivalente ao teorema das quatro cores.[25]

Uso fora da matemática

[editar | editar código-fonte]

Apesar da motivação de colorir mapas políticos de países, o teorema não é de interesse particular para os cartógrafos. De acordo com um artigo do historiador de matemática Kenneth May, "Mapas que utilizam apenas quatro cores são raros, pois geralmente requerem apenas três. Livros sobre cartografia e história da cartografia não mencionam a propriedade de quatro cores" (Wilson 2014, 2). O teorema também não garante a exigência cartográfica usual de que regiões não contíguas de um mesmo país (como o exclave do Alasca e o resto dos Estados Unidos) sejam coloridas de forma idêntica.

Referências

  1. From Gonthier (2008): "Definitions: A planar map is a set of pairwise disjoint subsets of the plane, called regions. A simple map is one whose regions are connected open sets. Two regions of a map are adjacent if their respective closures have a common point that is not a corner of the map. A point is a corner of a map if and only if it belongs to the closures of at least three regions. Theorem: The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors."
  2. Swart (1980).
  3. Wilson (2014), 216–222.
  4.    (25 de outubro de 2001). «Folha Online - Educação - Resumão/matemática - O teorema das quatro cores e o Mercosul - 25/10/2001 10h39». .folha.uol.com.br. Consultado em 20 de setembro de 2012 
  5. «The Four Color Theorem». Mathpages.com. Consultado em 20 de setembro de 2012 
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.