Teorema das catro cores

O teorema das catro cores é un teorema de formulación e conceptualización simple, mais de demostración extremadamente complexa. A súa formulación é a seguinte:
Dado un mapa plano, dividido en rexións, chegan catro cores para colorealo, de forma que rexións veciñas non partillen a mesma cor.

É necesario precisar un pequeno detalle: as rexións que só se tocan nun punto non se consideran veciñas. Sen esta condición, o teorema demostrouse pola primeira vez en 1976 por Appel e Haken, utilizando un computador IBM 360. En 1994 produciuse unha proba simplificada por Paul Seymour, Neil Robertson, Daniel Sanders e Robin Thomas, mais continúa a ser imposíbel demostrar o teorema sen recorrer a un computador.

A aplicación pode ser un mapa político de rexións e/ou países; as rexións pódense colorear, usando non máis de catro cores, sen que fiquen dúas rexións que se topan coa mesma cor. Cada rexión debe ser contigua, é dicir, non debe ter exclaves, tales como países como Angola, Azerbaidján ou os Estados Unidos de América.

Normalmente tres cores non chegan; este é o caso de se poñemos nun mapa unha rexión rodeada por outras tres rexións (aínda que para un número par de países circundantes tres cores cheguen) e tampouco é difícil de probar que abondan con cinco cores para pintar o mapa.

Importancia

O teorema das catro cores foi o primeiro teorema importante que se demostrou coa axuda dun computador, o que fixo que a demostración non se aceptase por todos os matemáticos debido a que non é factible para un ser humano verificar a demostración a man. No extremo, para crer nesa demostración, hai que ter fe na corrección do compilador e do hardware que executa o programa informático usado para probalo. Pola mesma razón, esta demostración por computador foi vista como pouco elegante.

En canto ao seu posíbel uso en cartografía, aínda que o teorema foi descuberto no proceso de colorear un mapa real, é moi raramente usado na práctica en cartografía, pois non parece haber tendencia a minimizar o número de cores usadas. A maioría dos mapas usan máis de catro cores. Ademais das rexións políticas con zonas non contiguas, os mares e lagos acostuman pórse nunha cor específica, co cal, se hai varios lagos ou mares, o teorema xa non se aplica como tal.

Categoría:Teoría de grafos
Catro cores, Teorema das
Categoría:Cor