Coloreando mapas

Imagen de Julee Juu extraída de Unsplash

Alguna vez, al mirar un mapa político del mundo, ¿te has preguntado cuántos colores diferentes hacen falta para pintarlo de modo que ningún par de países que compartan frontera tengan el mismo color?

Esta misma pregunta se la hizo el botánico y matemático Francis Guthrie en 1852 mientras intentaba colorear el mapa de los condados de Inglaterra. Guthrie notó que sólo necesitaba cuatro colores y le preguntó a su hermano (estudiante del célebre matemático Augustus De Morgan) si esto aplicaba a cualquier mapa posible.

Así nació el Teorema de los Cuatro Colores, uno de los problemas más famosos de la historia de las matemáticas. Durante más de un siglo, las mentes más brillantes intentaron demostrarlo sin éxito. No fue hasta 1976 cuando Kenneth Appel y Wolfgang Haken lograron la primera demostración matemática… ¡y lo hicieron con la ayuda de un ordenador! Fue la primera gran demostración matemática asistida por computación, lo que generó un enorme debate filosófico en la época.

El teorema establece que:

Cualquier mapa plano dividido en regiones contiguas puede ser coloreado usando como máximo cuatro colores, de forma que no existan dos regiones adyacentes con el mismo color.

(Nota: Dos regiones que sólo se tocan en un punto no se consideran adyacentes).

El problema de coloreado de grafos

Para la matemática, un mapa no es más que un grafo planar. Podemos representar cada país o región como un nodo (un punto) y trazar una arista (una línea) entre dos nodos si esos dos países comparten frontera.

Bajo esta perspectiva, el reto de Guthrie se convierte en el clásico Problema de Coloreado de Grafos, que es de vital importancia en la vida real. No sólo sirve para pintar mapas, sino que la misma lógica se aplica a la asignación de frecuencias de antenas de telefonía móvil (para que no haya interferencias), la programación de horarios de exámenes universitarios o la asignación de registros en compiladores informáticos.

El problema se puede plantear como un modelo de optimización lineal binaria, en el que se minimiza el número de colores usados en el coloreado de un mapa, ¿te atreves a intentarlo?

¿Quieres seguir explorando el mundo de la Investigación Operativa? Descubre más posts sobre el tema aquí.