El Teorema de los Cuatro Colores en la práctica

Quien trabaje en una empresa sabrá que los caminos del Señor son inexpugnables.


Antes de que penséis que se me ha ido la cabeza (cosa por otra parte muy razonable), dejarme que me explique. En una empresa acabas haciendo de todo. Es una máxima que se cumple al 100%, y más cuando en principio el informático eres tú.

Es por ello que tan pronto estás inverso en un proyecto de desarrollo para un evento, como haciendo una creatividad para un cartel, como publicando en el perfil de la red social que toque como un verdadero “Community Manager” de palo.

Y todo esto viene (aunque parezca imposible) como anillo al dedo al nombre de la entrada.

Hace escasos días, en una de esas mañanas en la oficina, me surgió la “impetuosa necesidad” de crear un mapa para la organización logística de un evento en uno de los hipódromos de nuestro país (no hace falta ser un investigador de prestigio para saber de cual estoy hablando).

Lo cierto es que aunque en principio abordé la empresa con la idea de hacer un dibujo a mano alzada, el poco tiempo del que disponía (una mañana) me hizo pronto prescindir de esta idea, decidiéndome por un estilo más sencillo con figuras planas hechas por photoshop.

Al ir incluyendo los numerosos elementos que conforman un mapa de evento, me encontré con un gran problema. Diferenciar sin tener que recurrir a diferentes colores, o mejor dicho, encontrar el método matemático para colorear secciones de un mapa de forma que ninguna de aquellas que estén pegadas tengan el mismo color.

Y aquí entra el Teorema de los Cuatro Colores:

Cualquier mapa geográfico puede ser coloreado con cuatro colores diferentes, de forma que no haya regiones adyacentes con el mismo color.

El teorema tiene ya más de 100 años entre nosotros, pero tuvieron que llegar Kenneth Appel y Wolfgang Haken con la demostración definitiva en 1976, y gracias a la capacidad de procesamiento de los ordenadores, comprobándolo con millones de mapas. Como suele ocurrir en estos casos, demostrar como verídico un teorema resulta extremadamente complejo, sin embargo basta encontrar un contraejemplo para tirar por traste todo el trabajo.

Afortunadamente (para Kenneth y Wolfgang, y en último término para mí), no hubo manera de encontrar un contraejemplo para el teorema, por lo que ha prevalecido desde entonces.

Investigando un poco más acabas descubriendo cosas sorprendentes, puesto que el teorema no solo se puede aplicar a mapas convencionales (rectangulares), sino que también se aplica sin problemas para circunferencias, para sectores de esferas, y ya deberíamos complicar el mapa hasta el punto de situarlo en una base toroidal (un donuts simétrico, para que nos entendamos), para que deje de servir como principio (en este caso pasaríamos a precisar 7 colores, en vez de 4).

Lo cierto es que este pequeño truco es más útil de lo que se piensa, ya que gracias a él, pude generar un mapa que funcionaba tan bien a color como en escala de grises (hay que prevenir los acontecimientos externos), cosa que no ocurría con el primero, multicolor y caótico.

P.D.: Existe un juego en Flash con decenas de mapas para colorear aplicando este principio. Su nombre es  Flood Fill, y ya os aviso que crea adición, y más cuando los mapas empiezan a complicarse y las posibles soluciones a restringirse.