El teorema de los 4 colores establece que cualquier mapa plano dividido en regiones, puede colorearse utilizando, como máximo, cuatro colores, de forma que ninguna región adyacente tenga el mismo color.
Propuesto inicialmente en 1852, el teorema fue formalmente probado en 1976 por Kenneth Appel y Wolfgang Haken, utilizando un enfoque computacional para verificar numerosos casos posibles. Es uno de los primeros resultados matemáticos en depender significativamente de las computadoras para su demostración. Este teorema es relevante en áreas como la teoría de grafos y cartografía.
Es una técnica utilizada para colorear grafos, siendo útil en la aplicación del teorema de los 4 colores. Este algoritmo organiza los vértices (regiones del mapa) en orden descendente según su grado (número de conexiones con otras regiones) y asigna colores a los vértices comenzando por los más conectados.
Ahora, se va a mostrar la aplicación a este algoritmo tomando el mapa de Colombia como ejemplo. Este mapa está dividido en departamentos y se desea colorear cada uno de estos, sin que hayan 2 departamentos vecinos (adyacentes) con el mismo color
Para facilitar la obtención del grado de cada uno, se optó por adaptar un archivo que contiene todas las regiones de los departamentos (Geojson original), añadiendole a cada departamento la propiedad "vecinos" que permitirá conocer tanto el grado y los departamentos que son adyacentes a este (Geojson adaptado).
Inicialmente se muestra el mapa de Colombia sin pintar, de allí vamos a partir para pintar todo el mapa
Para aplicar este algoritmo, inicialmente se debe de ordenar de mayor a menor grado cada uno de los departamentos
Luego, en ese orden, se elige un color (rojo) y se empieza a verificar si este departamento no ha sido pintato anteriormente y si no tiene vecinos con el mismo color a pintar (rojo en este caso)
Si se cumple con estas condiciones, el departamento se procede a pintar. Este paso se ejecuta para cada uno de los departamentos.
Como se puede observar, se completa la iteración y quedan algunos sin pintarse, estos se verificarán con el siguiente color
Los departamentos pintados quedan de esta manera:
Ahora se elige el siguiente color (verde) y como se hizo anteriormente, se pintan los que no se hayan pintado antes y los que no tengan vecinos ya pintados del color usado (verde).
Quedan faltando algunos por pintar, por lo que seguimos con el siguiente color
Los departamentos pintados quedan de esta manera:
Ahora se continúa con el azul y tendríamos algo parecido
Los departamentos pintados quedan de esta manera:
Finalizamos con el amarillo y así tendríamos el mapa completamente pintado
Los departamentos pintados quedan de esta manera: