El gráfico de cuatro colores es un problema matemático que plantea la siguiente pregunta: ¿Es posible colorear los vértices de un grafo plano con cuatro colores de modo que no existan dos vértices adyacentes con el mismo color?
Este problema puede parecer simple, pero su solución no lo es tanto. En efecto, el teorema de los cuatro colores, que establece que la respuesta a esta pregunta es sí, no fue probado hasta 1976, tras más de 100 años de intentos.
En este artículo, vamos a explorar este problema, explicando sus conceptos básicos y su importancia. También veremos algunas aplicaciones del gráfico de cuatro colores en la vida real.
Conceptos básicos:
Para entender el gráfico de cuatro colores, primero debemos definir algunos conceptos básicos.
Grafo: Un grafo es una colección de puntos, llamados vértices, y líneas, llamadas aristas, que conectan algunos de los vértices.
Grafo plano: Un grafo plano es un grafo que se puede dibujar en un plano sin que las aristas se crucen entre sí.
Coloración: Una coloración de un grafo es una asignación de un color a cada vértice de modo que no existan dos vértices adyacentes con el mismo color.
Número cromático: El número cromático de un grafo es el número mínimo de colores necesarios para colorear el grafo.
El problema:
El problema del gráfico de cuatro colores plantea la siguiente pregunta:
¿Cuál es el número cromático de un grafo plano?
En otras palabras, ¿es posible colorear los vértices de cualquier grafo plano con cuatro colores de modo que no existan dos vértices adyacentes con el mismo color?
La solución:
El teorema de los cuatro colores establece que la respuesta a esta pregunta es sí. En otras palabras, cualquier grafo plano puede ser coloreado con cuatro colores.
La primera demostración del teorema de los cuatro colores fue publicada en 1976 por Kenneth Appel y Wolfgang Haken. Su demostración fue una demostración por reducción al absurdo, que implicaba construir un conjunto infinito de grafos que, si no se cumpliera el teorema, tendrían que tener un número cromático mayor que cuatro.
La demostración de Appel y Haken fue muy controvertida, ya que utilizaba un ordenador para construir el conjunto infinito de grafos. Sin embargo, en 1997, el matemático Neil Robertson, junto con otros tres investigadores, publicó una demostración del teorema de los cuatro colores que no utilizaba un ordenador.
Aplicaciones en la vida cotidiana:
El gráfico de cuatro colores tiene una serie de aplicaciones en la vida real. Por ejemplo, se utiliza en la impresión offset, para colorear mapas y otros documentos que contienen regiones adyacentes.
También se utiliza en la teoría de la programación, para resolver problemas de asignación de recursos.
El gráfico de cuatro colores es un problema matemático sencillo de plantear, pero cuya solución no lo es tanto. El teorema de los cuatro colores es un resultado importante en la teoría de grafos, con aplicaciones en la vida real.
Atte. Patricio Figueroa M – Profesor de Matemáticas
