En 1736 el matemático Leonhard Euler visitó la ciudad de Königsberg, Alemania (actualmente Kaliningrado, Rusia) que constaba de cuatro partes separadas por un río, estando conectadas por siete puentes y donde había un pasatiempo local: encontrar cómo cruzar los siete puentes, caminado cada uno solo una vez terminando el recorrido en el punto de partida. Para resolver este acertijo, Euler dibujó un diagrama simple de puntos conectados por líneas (Figura 1), donde los puntos representaban las partes de la ciudad y las líneas indicaban cada puente: descubrió que era imposible resolver el desafío, porque cada parte de la ciudad tenía un número impar de puentes.
La representación elegida por Euler, un diagrama de puntos unidos por líneas parece surgir de manera natural en muchos escenarios, independientemente de su naturaleza, y es a partir del trabajo y el análisis que muchos científicos realizaron en sus respectivos campos, representando diversos problemas con puntos conectados por líneas, cuando surgió lo que se conoce como teoría de grafos.
En este contexto cabe decir que, aun cuando Fran Harary es comúnmente aceptado como el padre de la teoría moderna de los grafos, en parte gracias a la publicación de su libro “Graph Theory” en 1969, esta teoría no comenzó como una única entidad monolítica y no puede atribuirse a una sola persona. Científicos, como William Thomas Tutte, Edsger Wybe Dijkstra y Paul Erdös, entre otros, contribuyeron en gran medida a su desarrollo y difusión.
La teoría de grafos ha adquirido una importancia creciente gracias a sus múltiples aplicaciones, más allá de las matemáticas puras. Los grafos son ampliamente utilizados en ciencias sociales, ingeniería y, particularmente, en ciencias de la computación.
Para dar ejemplos concretos, en química, una molécula puede representarse como un conjunto de elementos interconectados. También es posible emplear grafos para modelar redes intrincadas de carreteras que unen distintas ciudades, empleando puntos para representar las ciudades y líneas entre ellos para marcar las carreteras. Adicionalmente, a estas líneas se les puede asignar valores que indiquen, por ejemplo, la distancia entre ciudades.
Esta última representación está asociada con un problema famoso, denominado problema del agente viajero: dado un conjunto de ciudades y una red de caminos entre ellas, encontrar la trayectoria más corta que le permita a un agente de ventas visitar todas las ciudades.
Al igual que el acertijo de los puentes de Königsberg, el problema del agente viajero surgió de situaciones de la vida real. Existe otro desafío, por demás interesante, que emerge de lo que podría llamarse un problema cotidiano: el coloreo de mapas.
Grafos y mapas
El problema de la coloración de grafos tiene su origen en la práctica común de colorear mapas (Figura 2), asignando diferentes colores a regiones adyacentes. Francis Guthrie en 1852 observó que un mapa con los condados de Inglaterra requería solo cuatro colores para ser coloreado sin que las regiones vecinas compartieran el mismo color. Luego, sin éxito, intentó encontrar un mapa que necesitara más de cuatro colores.
A través de su hermano menor, este asunto llegó a oídos de Augustus De Morgan, quien se interesó en el problema. Más tarde, varios matemáticos intentaron encontrar una prueba matemática de que cualquier mapa se pudiera colorear con no más de cuatro colores. Con el paso del tiempo, este problema llegó a ser conocido como el Problema de los Cuatro Colores.
En 1878, Alfred Bray Kempe asistió a una reunión de la Sociedad Matemática de Londres, donde escuchó sobre el Problema de los Cuatro Colores y, en 1879 presentó en la revista Nature lo que creyó era la prueba de que cualquier mapa podría ser coloreado con no más de cuatro colores. Su prueba parecía correcta y fue ampliamente aceptada, pero en 1890 el matemático Percy John Heawood proporcionó un contraejemplo, demostrando que el razonamiento empleado era defectuoso. Aunque el trabajo de Kempe era incorrecto, el Problema de los Cuatro Colores prevaleció pues nadie había encontrado un mapa que necesitara más de cuatro colores para ser coloreado. De hecho, Heawood demostró que el método de Kempe era la prueba de que cualquier mapa podría ser coloreado con no más de cinco colores.
A pesar del esfuerzo y el trabajo de muchos matemáticos, la pregunta de si un mapa podría necesitar al menos cinco colores para ser coloreado quedó sin respuesta durante varias décadas: los matemáticos enfocaron sus esfuerzos en reducir cada mapa a un conjunto de configuraciones inevitables de regiones. Este enfoque se basa en la reducibilidad, un concepto introducido por George David Birkhoff.
La idea básica es exhibir un “conjunto inevitable” de “configuraciones reducibles”. Éstas son arreglos locales de regiones que no pueden aparecer en un contraejemplo más pequeño porque su presencia en un mapa implica que éste se puede colorear a partir de un mapa más pequeño por inducción, y un conjunto de configuraciones es inevitable si cada mapa contiene al menos una configuración del conjunto.
Esta búsqueda de cada configuración dentro del mapa implica una carga de trabajo que consume mucho tiempo, volviéndolo impráctico de hacer a mano, lo que llevó, a fin de la década de 1960 a Heinrich Heesch, Wolfgang Haken, Karl Dürre y Yoshio Shimamoto, y luego Kenneth Appel, a considerar el uso de computadoras para ayudar en la demostración. En junio de 1976, Appel y Haken construyeron un conjunto inevitable de 1936 configuraciones reducibles, demostrando la Conjetura de los Cuatro Colores con la primera prueba matemática asistida por computadora.
Este problema, que perduró durante siglos y que a simple vista se limita a una curiosidad cartográfica, en realidad puede ayudar a resolver diversos problemas con aplicaciones muy prácticas, mediante el coloreo de grafos.
Informalmente un grafo es un dibujo o esquema, sin embargo, cuando un grafo cuenta con un gran número de nodos y conexiones, resulta difícil o hasta imposible dibujarlo por completo. Adicionalmente, si deseamos asistirnos de una computadora para trabajar con el grafo, primero es necesario formular una definición formal y una forma de representación adecuada.
Un grafo se define como una entidad compuesta por un conjunto (no vacío) V de puntos llamados vértices y un segundo conjunto E (que sí puede ser vacío) de líneas llamadas aristas:
G=(V,E)
donde
V={v_0, v_1,…, v_n}
y
E={e_0, e_1,…, e_m}
Cada arista de E se define como un par {u, v}, donde u, v ∈ V y se dice que son vértices adyacentes, el número n de vértices en un grafo se conoce como su orden, mientras que el número m de aristas en un grafo se asigna su tamaño, y al número de aristas incidentes en un vértice v de G se llama el grado de v y se expresa como dG(v).
Colorear un grafo G con una coloración adecuada significa asignar colores (o etiquetas) a sus vértices de forma que los vértices adyacentes siempre tengan colores diferentes. El problema de la coloración de grafos consiste entonces, en buscar una coloración adecuada para un grafo dado, asignando el número mínimo de colores.
Puede haber varias coloraciones adecuadas para un grafo, pero si el número de colores utilizados para una coloración adecuada es mínimo, entonces la cardinalidad del conjunto de colores C = 1,2,…,k (|C|) se conoce como el número cromático de G y se representa como χ(G) = m.
La coloración de grafos ha sido una fuente rica de algoritmos en ciencias de la computación, puesto que tiene muchas aplicaciones prácticas, sin embargo, muchos de ellos pueden ser eficientes únicamente al aplicarse a grafos con características especiales, como son los grafos planos o los bipartitos.
Cuando χ(G)>2, el problema se vuelve NP-completo, es decir, que no se conoce un algoritmo que pueda encontrar una solución en un tiempo razonable: colorear un grafo G significa probar todas las posibles asignaciones entre V y C, cuando |C|=3, y si no se encuentra una coloración adecuada, repetir cuando |C|=4 y continuar aumentando el número de colores hasta encontrar una coloración adecuada. Es por ello, que encontrar la solución óptima para un grafo pequeño puede ser factible, pero el costo computacional se vuelve prohibitivo para un grafo grande. Alternativamente se puede utilizar el algoritmo de retroceso (backtracking) para encontrar no solo una solución óptima, sino también todas las coloraciones propias, incluidas las mínimas.
En lugar de utilizar una búsqueda exhaustiva de la solución óptima, es posible primero verificar si el grafo pertenece a algún tipo particular que permita reducir en gran medida las posibilidades. Por ejemplo, si G={V,E} es un grafo completo (cada vértice es adyacente a los demás vértices), significa que cada vértice necesita su propio color. Si |V|=k, entonces χ(G)=k para un grafo completo.
Otro tipo especial de grafo cuyo número cromático se conoce es el de los grafos bipartitos, es decir, aquellos grafos cuyo conjunto de vértices puede subdividirse en dos conjuntos disjuntos e independientes V1 y V2. Esto significa que cada vértice en V1 solo tiene adyacencias a vértices en V2, y cada vértice en V2 solo tiene adyacencias a vértices en V1; cada vértice en V1 comparte un color y cada vértice en V2 comparte un segundo color, por lo tanto, el número cromático de cualquier grafo bipartito es 2.
Si un grafo no posee una característica especial que permita una simplificación del problema, se puede utilizar una heurística: una regla o estrategia que permita simplificarlo; este enfoque no garantizará obtener la solución óptima, pero obtendrá una solución lo suficientemente buena en un tiempo razonable. En la literatura es común encontrar algoritmos de coloración de grafos de este tipo, como el algoritmo voraz de coloreo, el algoritmo de Welsh-Powell o el algoritmo de DSatur, entre otros.
Relevancia de la coloración de grafos
La coloración de grafos se utiliza ampliamente en la investigación de las ciencias de la computación en campos como redes, minería de datos y el procesamiento de imágenes. Los problemas de programación o scheduling (planeación de tareas) son aplicaciones típicas de la coloración de grafos. En telecomunicaciones, la coloración de grafos tiene aplicaciones prácticas en la planificación de redes de acceso por radio para asignar canales o códigos en redes móviles, mientras que en nuestras computadoras se usan para gestionar el uso de registros por parte del microprocesador y como se mencionó, la coloración de mapas es una actividad más antigua que la teoría de grafos en sí misma, siendo una aplicación muy común de la coloración de grafos.
Conclusión
Aunque los grafos pueden parecer interesantes solo desde un punto de vista recreativo para aquellos que los conocen por primera vez, la realidad es que son una herramienta muy útil para resolver una amplia variedad de problemas en la vida real: si un problema se puede representar mediante un grafo, es posible que a través de la teoría de grafos se pueda abordar y resolver.
Este es el caso de la coloración de mapas con la que comenzó el estudio de la coloración de grafos y que, como se puede ver en este trabajo, tiene múltiples aplicaciones prácticas en diversos campos, convirtiendo este problema en un tema importante de estudio en la informática.
Debido a su complejidad, la coloración de grafos solo se puede resolver completamente mediante técnicas combinatorias, probando cada configuración posible, lo que puede llevar mucho tiempo incluso para grafos medianos, por lo que el enfoque de fuerza bruta solo se puede utilizar para grafos pequeños. Sin embargo, mediante heurísticas es posible encontrar respuestas lo suficientemente buenas en un tiempo razonable. Estas soluciones son especialmente útiles en problemas que requieren la optimización de recursos o la asignación de tareas para evitar posibles conflictos, adquiriendo una gran importancia en la actualidad, lo que probablemente llevará a la búsqueda de nuevos algoritmos de coloración de grafos en los próximos años.
Referencias
Alsina, C. (2010). Mapas del metro y redes neuronales: la teoría de grafos.
Appel, K., & Haken, W. (1977). Every planar map is four colorable. Part I: Discharging. Illinois Journal Of Mathematics, 21(3). https://doi.org/10.1215/ijm/1256049011
Appel, K., Haken, W., & Koch, J. (1977). Every planar map is four colorable. Part II: Reducibility. Illinois Journal Of Mathematics, 21(3). https://doi.org/10.1215/ijm/1256049012Bondy, J. A., & Murty, U. S. R. (1976). Graph Theory with Applications. https://doi.org/10.1007/978-1-349-03521-2
Wilson, R. (2014). Four colors suffice: How the map problem was solved. En Princeton University Press eBooks. https://doi.org/10.1515/9780691237565
*Foto de portada creada con la ayuda de ChapGPT
