escritorio

Teorema de los cuatro colores


Ejemplo de mapa coloreado con cuatro colores.


Mapa del mundo coloreado de verde, amarillo, azul y rojo.
En teoría de grafos, el teorema de cuatro colores es un teorema sobre la coloración de grafos que establece lo siguiente:
Dado cualquier mapa geográfico con regiones continuas, éste puede ser coloreado con cuatro colores diferentes, de forma que noqueden regiones adyacentes con el mismo color.
Asumiendo que las regiones adyacentes comparten no solo un punto, sino todo un segmento de borde (frontera) en común.
Tres colores son suficientes para mapas simples, pero en algunos casos es necesario un cuarto color adicional, esto es, cuando una región a colorear queda encerrada por un número impar de regiones que se tocan formando un ciclo. Elteorema de los cinco colores, cuya demostración es corta y elemental, establece que cinco colores son suficientes para colorear un mapa y fue probado en el siglo XIX por Heawood.1 Una serie de pruebas falsas y falsos contraejemplos han aparecido desde el primer enunciado del teorema de los cuatro colores en 1852.
El problema del mapa de cuatro colores fue planteado, por primera vez, por el estudianteFrancis Guthrie en 1852, lo que fue comunicado a Augustus de Morgan.2 La conjetura se hizo famosa con la declaración de Arthur Cayley, en 1878, en el sentido de que la había abordado. Fue resuelto, a mediados de 1970, por Kenneth Appel y Wolfgang Haken.3


Ejemplo de un mapa de Azerbaijan con regiones no continuas
Índice [ocultar]
1 Formulación precisa del teorema
2 La polémicademostración
3 Resumen de las ideas de la demostración
4 Generalizaciones
5 Referencias
6 Bibliografía
7 Enlaces externos
Formulación precisa del teorema[editar · editar fuente]

En primer lugar, todas las esquinas y puntos en común que pertenecen a tres o más países, deben ser ignoradas. Sin esta restricción, los mapas extraños (utilizando las regiones del área finita pero perímetro infinito) puedenrequerir más de cuatro colores.
En segundo lugar, para el propósito del teorema cada "país" tiene que ser una región simplemente conexa o continua. En el mundo real, esto no es cierto (por ejemplo, Alaska como parte de los Estados Unidos, Nakhchivan como parte de Azerbaiyán, y Kaliningrado como parte de Rusia no son regiones continuas). Debido a que el territorio de un país en particular debe serdel mismo color, cuatro colores no son suficientes. Por ejemplo, considérese un mapa simplificado:
4CT Inadequacy Example.svg
En este mapa, las dos regiones A pertenecen a un mismo país, y por lo tanto, deben ser del mismo color. En consecuencia, este mapa requiere cinco colores, puesto que las dos regiones A son contiguas con las otras cuatro regiones, y cada una de estas regiones soncontiguas entre sí. Si hay tres regiones A, entonces se necesitan seis o más colores; se pueden construir mapas que requieren un número arbitrariamente elevado de colores. Un escenario similar también se puede dar si el color azul se reserva para el agua.


Mapa y grafo dual asociado.
Una versión más simple del teorema utiliza la teoría de grafos. El conjunto de las regiones de un mapa se puederepresentar de manera más abstracta como un grafo simple no dirigido asociando un vértice para cada región y una arista para cada par de regiones que comparten un segmento de borde. Esta representación del mapa con vértices y aristas es un grafo dual y el problema de colorear países se cambia por la coloración del grafo. Este grafo es plano, o sea, que se puede dibujar en el plano sin cruce de aristasmediante la colocación de cada vértice en un lugar elegido arbitrariamente dentro de la región a la que corresponde. Con la terminología de la teoría de grafos, el teorema de cuatro colores establece que:
Teorema de los 4 colores. Si G \, es un grafo plano, entonces \chi(G) \le 4
Es decir, los vértices de cada grafo plano pueden ser coloreados con un máximo de cuatro colores de modo que no...