Pintor de mapas del teorema de los cuatro colores
Por complicado que sea un mapa, cuatro colores bastan siempre para colorearlo de modo que los países que comparten frontera nunca compartan color. El enunciado es tan sencillo que un niño puede ponerlo a prueba con lápices de colores, y sin embargo hicieron falta más de un siglo y un ordenador para demostrarlo. Pinta tú mismo un mapa aleatorio, mira qué fronteras están en conflicto y luego observa cómo lo hacen tres métodos, desde una rápida regla voraz que a veces necesita un quinto color hasta una búsqueda con vuelta atrás que siempre se arregla con cuatro. Elige un color y haz clic en los países para pintarlos; una frontera se vuelve roja cuando dos vecinos comparten color. Los países que solo se tocan en una esquina pueden compartirlo. O deja que lo haga el ordenador: elige un método y pulsa Resolver para verlo trabajar, o Paso para seguirlo movimiento a movimiento. Mínimo de colores comprueba si a este mapa le bastarían tres colores, o incluso dos. Nuevo mapa dibuja otro mapa, y Mostrar los vecinos dibuja la red de países que comparten frontera.
Cómo funciona
- Elige el número de países y pulsa Nuevo mapa, o empieza con el mapa que se muestra.
- Elige un color y haz clic en los países para pintarlos, atento a las fronteras rojas donde los vecinos entran en conflicto.
- Elige un método y pulsa Resolver o Paso para ver cómo colorea el mapa, y pulsa Mínimo de colores para ver cuántos colores necesita este mapa.
De los mapas a los grafos
Pon un punto en cada país y une dos puntos cuando sus países compartan frontera. El mapa se convierte en un grafo, y colorear el mapa equivale a colorear los puntos de modo que los puntos unidos sean distintos. Como los mapas se dibujan en una hoja plana, estos grafos son planos: se pueden dibujar sin que las líneas se crucen. Los países que se encuentran en un único punto, como cuatro cuadrados en una esquina, no son vecinos. El teorema de los cuatro colores dice que todo grafo plano puede colorearse con cuatro colores. Activa Mostrar los vecinos para ver el grafo del mapa actual.
Tres formas de colorear
La coloración voraz toma los países de uno en uno, primero los que tienen más vecinos, y da a cada uno el primer color que sus vecinos no han usado. Es rápida pero miope, y en algunos mapas recurre a un quinto o incluso un sexto color. DSATUR, inventado por Daniel Brélaz en 1979, elige siempre a continuación el país cuyos vecinos ya muestran más colores distintos, lo que suele evitar esa trampa. La vuelta atrás prueba los colores por turno y, cuando a un país no le queda ninguno, deshace sus decisiones más recientes y vuelve a intentarlo; siempre encuentra una coloración con cuatro colores, a veces después de retroceder muchas veces.
Preguntas frecuentes
¿Por qué bastan siempre cuatro colores?
Nadie ha encontrado una razón breve. La demostración de Kenneth Appel y Wolfgang Haken de 1976 mostró que todo mapa debe contener una de 1936 pequeñas configuraciones, y que cada una de ellas puede eliminarse y la coloración restaurarse después; comprobarlas todas llevó más de mil horas de cálculo por ordenador. Una demostración por ordenador más sencilla de Neil Robertson, Daniel Sanders, Paul Seymour y Robin Thomas de 1996 necesita 633 configuraciones, y en 2005 Georges Gonthier verificó una demostración por completo con el asistente de demostración Coq.
¿Hay mapas que necesitan los cuatro colores?
Sí. Cuatro países que tocan cada uno a los otros tres, como un país rodeado por un anillo de otros tres, necesitan cuatro. Muchos mapas, en cambio, se arreglan con tres, y Mínimo de colores lo averigua para el mapa de la pantalla. Decidir en general si un mapa puede colorearse con tres colores es un problema difícil, NP-completo, aunque cuatro colores bastan siempre.
¿Por qué el método voraz usa a veces cinco colores?
Colorea cada país una sola vez y nunca cambia de opinión. Una elección temprana puede dejar a un país posterior rodeado por los cuatro colores, y la única salida es un quinto. La vuelta atrás, en cambio, retrocedería y cambiaría las elecciones anteriores.
¿Se cumple el teorema en otras superficies?
En una esfera, sí: es lo mismo que el plano. En un toro, la superficie de un dónut, algunos mapas necesitan siete colores, y siete bastan siempre, como demostró Percy Heawood. Si los países pueden constar de varias piezas separadas, como una nación con colonias, cuatro colores ya no bastan.
¿Se envía algo a un servidor?
No. El mapa, los métodos de coloración y la comprobación se ejecutan en tu navegador. Tus ajustes se quedan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor