El teorema de los cuatro colores explicado
En 1852, un joven matemático que coloreaba un mapa de los condados de Inglaterra observó que cuatro colores parecían bastar para distinguir los condados vecinos. ¿Podía ser cierto para cualquier mapa posible? La pregunta se convirtió en uno de los problemas más famosos de las matemáticas, atrajo una célebre demostración falsa que se mantuvo once años y finalmente se resolvió en 1976 de una manera que cambió lo que los matemáticos aceptan como demostración.
La pregunta
Francis Guthrie, antiguo alumno de Augustus De Morgan, preguntó si cualquier mapa puede colorearse con cuatro colores de modo que los países que comparten frontera reciban colores distintos. Dos reglas precisan la pregunta. Los países deben ser conexos, cada uno de una sola pieza, y los países que solo se encuentran en un único punto no cuentan como vecinos. Está claro que tres colores no siempre bastan, ya que un país rodeado por un anillo de otros tres que se tocan entre sí necesita un cuarto. La pregunta es si alguna vez hace falta un quinto.
Los mapas como grafos
Marca un punto en cada país y traza una línea entre dos puntos siempre que sus países compartan frontera. El resultado es un grafo y, como el mapa está sobre una hoja plana, las líneas pueden trazarse sin cruzarse: el grafo es plano. Colorear el mapa es colorear los vértices de este grafo de modo que los extremos de cada arista sean distintos. El menor número de colores que funciona es el número cromático, y el teorema de los cuatro colores afirma que ningún grafo plano tiene un número cromático mayor que cuatro.
La demostración fallida de Kempe
En 1879, el abogado y matemático Alfred Kempe publicó una demostración. Su ingeniosa idea, hoy llamada cadenas de Kempe, consiste en intercambiar dos colores a lo largo de una cadena conexa de países para liberar un color donde hace falta. La demostración se aceptó durante once años, hasta que Percy Heawood encontró un fallo en 1890. La reparación de Heawood demostró un resultado más débil: cinco colores bastan siempre. Las cadenas de Kempe sobrevivieron y se convirtieron en una herramienta de la demostración definitiva.
Por qué cinco es fácil
Todo grafo plano tiene un vértice con a lo sumo cinco vecinos; esto se deduce de la fórmula de Euler, que limita un grafo plano con n vértices a como mucho 3n − 6 aristas. Quita un vértice así, colorea el resto del mapa con el mismo argumento y vuelve a poner el vértice. Si sus vecinos usan menos de cinco colores, queda uno libre. Si usan los cinco, un intercambio a lo largo de una cadena de Kempe siempre libera uno. Con cuatro colores, el mismo intercambio puede fallar, y ese es exactamente el fallo que Kempe pasó por alto.
La demostración por ordenador
En 1976, Kenneth Appel y Wolfgang Haken, de la Universidad de Illinois, demostraron el teorema. Mostraron que todo mapa contiene al menos una de 1936 configuraciones de un conjunto inevitable, y que cada configuración es reducible: un mapa mínimo que necesitara cinco colores no podría contenerla. Comprobar la reducibilidad llevó más de mil horas de ordenador, demasiado para verificarlo a mano. Muchos matemáticos se sentían incómodos con una demostración que ninguna persona podía leer entera, y comenzó el debate sobre las demostraciones asistidas por ordenador.
Demostraciones más sencillas y verificación completa
En 1996, Neil Robertson, Daniel Sanders, Paul Seymour y Robin Thomas publicaron una demostración más sistemática con 633 configuraciones, todavía comprobada por ordenador pero más fácil de verificar. En 2005, Georges Gonthier y Benjamin Werner formalizaron la demostración completa en el asistente de demostración Coq, de modo que un programa pequeño y de confianza comprueba cada paso lógico. Hoy, el teorema de los cuatro colores es uno de los resultados más minuciosamente verificados de las matemáticas.
Algoritmos de coloración
Encontrar una coloración con cuatro colores de un mapa dado es rápido en la práctica, pero encontrar el menor número de colores para un grafo cualquiera es difícil: decidir si bastan tres colores es NP-completo. Entre los métodos prácticos están la coloración voraz por orden de grado decreciente, DSATUR, que colorea a continuación el vértice más restringido, y la búsqueda con vuelta atrás, que explora opciones y las deshace cuando se atasca. La coloración de grafos sirve para programar exámenes sin coincidencias, asignar frecuencias de radio para que los transmisores vecinos no se interfieran y asignar registros en los compiladores.
Explóralo
Abre el pintor de mapas de los cuatro colores para generar mapas de 4 a 120 países, pintarlos a mano con cuatro colores y ver cómo aparecen los conflictos en rojo. Deja que la coloración voraz, DSATUR o la vuelta atrás resuelvan el mapa paso a paso, muestra el grafo de los países vecinos y comprueba cuántos colores necesita realmente el mapa como mínimo.
Preguntas frecuentes
¿Ayuda el teorema a los cartógrafos?
Apenas. Los mapas reales suelen colorearse con más colores para mayor claridad, e incluyen océanos, lagos y países en varias piezas, que el teorema no contempla. Su importancia es matemática: impulsó el desarrollo de la teoría de grafos y planteó la cuestión de qué cuenta como demostración.
¿Qué es una cadena de Kempe?
Toma dos colores, por ejemplo rojo y azul, y un país coloreado de rojo. Su cadena de Kempe es el conjunto de todos los países rojos y azules a los que puedes llegar desde él pasando solo por vecinos rojos y azules. Intercambiar rojo y azul en toda la cadena mantiene válida la coloración y puede liberar un color para un país junto a la cadena.
¿Por qué los países en varias piezas rompen el teorema?
Si un país puede constar de regiones separadas que deben tener todas el mismo color, el grafo de vecinos deja de ser plano, y se pueden construir mapas que necesiten cualquier número de colores hasta 12 con dos piezas por país, como estudió Heawood en su problema de los imperios.
¿Por qué el pintor crea los mapas a partir de puntos?
Cada país es la región del cuadrado más cercana a un punto aleatorio que a cualquier otro, un diagrama de Voronoi. Así se obtienen mapas de aspecto realista con países convexos, y dos países son vecinos exactamente cuando sus regiones comparten un tramo de frontera, algo que la aplicación calcula con precisión.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Abrir el pintor de mapas de los cuatro colores