Introducción
es la tarea computacional de asignar colores a los elementos de un gráfico de modo que los elementos adyacentes nunca compartan el mismo color. Tiene aplicaciones en varios dominios, incluida la programación deportiva, la cartografía, la navegación por mapas de calles y la programación de horarios. También es de gran interés teórico y una materia estándar en cursos de nivel universitario sobre teoría de grafos, algoritmos y combinatoria.
Un gráfico es una estructura matemática que comprende un conjunto de nodos en los que algunos pares de nodos están conectados por aristas. Dada cualquier gráfica,
Una coloración de nodos es una asignación de colores a los nodos de modo que todos los pares de nodos unidos por aristas tengan colores diferentes. Una coloración de aristas es una asignación de colores a las aristas para que todas las aristas que se encuentran en un nodo tengan colores diferentes. Una coloración de caras de un gráfico es una asignación de colores a las caras de una de sus incrustaciones planas (si existe tal incrustación) de modo que las caras con límites comunes tengan colores diferentes.
En las imágenes de arriba se muestran ejemplos de estos conceptos. Observe en el último ejemplo que los colores de caras requieren que los nodos estén dispuestos en el plano de manera que ninguno de los bordes del gráfico se cruce. En consecuencia, sólo son posibles para gráficos planos. Por el contrario, la coloración de nodos y bordes es posible para todos los gráficos. El objetivo es encontrar colorantes que utilicen el número mínimo (óptimo) de colores, lo cual es un problema NP difícil en general.
Los artículos de este foro (aquí, aquí y aquí) han considerado previamente la coloración de gráficos, centrándose principalmente en heurísticas constructivas para el problema de coloración de nodos. En este artículo consideramos los colores de nodos, bordes y caras y buscamos darle vida al tema a través de ejemplos detallados y visualmente atractivos. Para hacer esto, utilizamos la biblioteca GCol recién creada, una biblioteca Python de código abierto construida sobre NetworkX. Esta biblioteca utiliza algoritmos exactos de tiempo exponencial y heurísticas de tiempo polinomial.
El siguiente código Python utiliza GCol para construir y visualizar los colores de nodos, bordes y caras del gráfico que se ve arriba. Una lista completa del código utilizado para generar las imágenes de este artículo está disponible aquí. Una versión ampliada de este artículo también está disponible aquí.
importar networkx como nx importar matplotlib.pyplot como plt importar gcol G = nx.dodecahedral_graph() # Generar y mostrar un color de nodo c = gcol.node_coloring(G) nx.draw_networkx(G, node_color=gcol.get_node_colors(G, c)) plt.show() # Generar y mostrar un color de borde c = gcol.edge_coloring(G) nx.draw_networkx(G, edge_color=gcol.get_edge_colors(G, c)) plt.show() # Genera posiciones de nodos y luego un color de cara pos = nx.planar_layout(G) c = gcol.face_coloring(G, pos) gcol.draw_face_coloring(c, pos) nx.draw_networkx(G, pos) plt.mostrar()
Coloración de nodos
La coloración de nodos es el más fundamental de los problemas de coloración de gráficos. Esto se debe a que los problemas de coloración de aristas y caras siempre se pueden convertir en instancias del problema de coloración de nodos. Específicamente:
Se puede lograr una coloración de bordes de un gráfico coloreando los nodos de su gráfico lineal. Se puede encontrar una coloración de caras de un gráfico plano coloreando los nodos de su gráfico dual.
Los problemas de coloración de aristas y caras son, por tanto, casos especiales del problema de coloración de nodos, relacionados con gráficos lineales y gráficos planos, respectivamente.
Al visualizar los colores de los nodos, la ubicación espacial de los nodos afecta la interpretabilidad. Los buenos diseños de nodos pueden revelar patrones estructurales, grupos y simetrías, mientras que los diseños deficientes pueden oscurecerlos. Una opción es utilizar métodos dirigidos por la fuerza, que modelan los nodos como elementos que se repelen mutuamente y los bordes como resortes. Luego, el método ajusta las posiciones de los nodos para minimizar una función de energía, equilibrando las fuerzas de atracción de los bordes y las fuerzas repulsivas de los nodos. El objetivo es crear un diseño estéticamente agradable donde los grupos de nodos relacionados estén cerca, los nodos no relacionados estén separados y pocos bordes se crucen.
Los colores de las imágenes de arriba demuestran los efectos de diferentes esquemas de posicionamiento de nodos. El primer ejemplo utiliza posiciones seleccionadas al azar, lo que parece dar un diagrama bastante desordenado. El segundo ejemplo utiliza un método dirigido por la fuerza (específicamente, la rutina spring_layout() de NetworkX), lo que da como resultado un diseño más lógico en el que las comunidades y la estructura son más evidentes. GCol también permite posicionar los nodos según sus colores. La tercera imagen posiciona los nodos en la circunferencia de un círculo, colocando nodos del mismo color en posiciones adyacentes; el segundo organiza los nodos de cada color en columnas. En estos casos, la estructura de la solución es más evidente y es más fácil observar que nodos del mismo color no pueden tener aristas entre sí.
Los colores de los nodos suelen ser más fáciles de mostrar cuando el número de aristas y colores es pequeño. A veces, los nodos también tienen una posición natural que ayuda a la interpretación. En las siguientes imágenes se muestran ejemplos de dichos gráficos. Los tres primeros muestran ejemplos de gráficos bipartitos (gráficos que sólo necesitan dos colores); el resto muestra gráficos que requieren tres colores.
Coloración de bordes
La coloración de bordes requiere que todos los bordes que terminan en un nodo particular tengan un color diferente. Como resultado, para cualquier gráfico GG, el número mínimo de colores necesarios es siempre mayor o igual a Δ(G)\Delta(G), donde Δ(G)\Delta(G)denota el grado máximo en GG. Para gráficos bipartitos, el teorema de Konig nos dice que los colores Δ(G)\Delta(G) siempre son suficientes.
El teorema de Vizing da un resultado más general, afirmando que, para cualquier gráfico GG, no se necesitan más de Δ(G)+1\Delta(G)+1 colores.
La coloración de bordes tiene aplicaciones en la construcción de ligas deportivas, donde se requiere que un conjunto de equipos jueguen entre sí durante una serie de rondas. El primer ejemplo anterior muestra un gráfico completo en seis nodos, un nodo por equipo. Aquí, los bordes representan partidos entre equipos y cada color representa una única ronda en el calendario. Por lo tanto, la ronda “azul oscuro” involucra partidos entre los equipos 0 y 1, 2 y 3, y 4 y 5, por ejemplo. Las otras imágenes de arriba muestran colores de borde óptimos de dos de los gráficos vistos anteriormente. Estos ejemplos recuerdan a los patrones de tapetes de crochet o, quizás, a los atrapasueños ojibwe.
A continuación se muestran los colores de los bordes de dos gráficos más. Estos ayudan a ilustrar cómo, utilizando la coloración de bordes, los recorridos alrededor de un gráfico se pueden especificar mediante un nodo inicial y una secuencia de colores que especifican el orden en el que se siguen los bordes. Esto proporciona una forma alternativa de especificar rutas entre ubicaciones en mapas de calles.
colorear la cara
El famoso teorema de los cuatro colores establece que la coloración de caras de incrustaciones planas nunca requiere más de cuatro colores. Este fenómeno fue observado por primera vez en 1852 por Francis Guthrie mientras coloreaba un mapa de los condados de Inglaterra; sin embargo, se necesitarían más de 100 años de investigación para demostrarlo formalmente.
Las imágenes de arriba muestran los colores de las caras de tres gráficos. Aquí, se deben asumir nodos dondequiera que se vea que los bordes se unen. En esta figura, la cara central del gráfico de Thomassen ilustra por qué a veces se necesitan cuatro colores. Como se muestra, esta cara central es adyacente a cinco caras circundantes. Juntas, estas cinco caras forman un ciclo de longitud impar, que necesariamente requiere tres colores diferentes, por lo que la cara central debe asignarse a un cuarto color. Sin embargo, nunca será necesario un quinto color.
Sin embargo, los colorantes faciales suelen necesitar menos de cuatro colores. Para demostrar esto, aquí consideramos un tipo especial de gráfico conocido como gráfico euleriano. Este es simplemente un gráfico en el que los grados de todos los nodos son pares. Un grafo plano es euleriano si y sólo si su grafo dual es bipartito; en consecuencia, las caras de los gráficos planos eulerianos siempre se pueden colorear con dos colores.
Arriba se muestran ejemplos de esto donde, según sea necesario, todos los nodos tienen un grado par. Se pueden ver ejemplos prácticos de este teorema en tableros de ajedrez, patrones de espirógrafo y muchas formas de arte islámico y celta, todos los cuales presentan gráficos subyacentes que son tanto planos como eulerianos. Los patrones de mosaico comunes que involucran mosaicos cuadrados, rectangulares o triangulares también se caracterizan por dichos gráficos, como se ve en el conocido estilo de mosaico “a cuadros”.
A continuación se muestran otros dos patrones de mosaico. El primero utiliza azulejos hexagonales, donde el cuerpo principal presenta un patrón repetido de tres colores. El segundo ejemplo muestra una coloración óptima de un patrón de mosaico aperiódico descubierto recientemente. Aquí los cuatro colores se distribuyen de forma menos regular.
Nuestro último ejemplo proviene de un infame artículo falso de una edición de 1975 de Scientific American. Una de las afirmaciones falsas hechas en este artículo fue que se había descubierto un gráfico cuyas caras necesitaban al menos cinco colores, refutando así el teorema de los cuatro colores. Este gráfico se muestra a continuación, junto con cuatro colores.
Conclusiones y recursos adicionales
El artículo revisó y visualizó varios resultados del campo de la coloración de gráficos, utilizando la biblioteca Python de código abierto GCol. Al principio, observamos varias aplicaciones prácticas importantes de este problema, lo que demuestra su utilidad. Este artículo se ha centrado en los aspectos visuales, demostrando que también es bonito.
El teorema de los cuatro colores surgió de la observación de que, al colorear territorios en un mapa geográfico, no se necesitan más de cuatro colores. A pesar de esto, los cartógrafos no suelen estar interesados en limitarse a sólo cuatro colores. De hecho, es útil que los mapas también satisfagan otras restricciones, como garantizar que todos los cuerpos de agua (y ninguna superficie terrestre) sean de color azul, y que las áreas separadas del mismo país (como Alaska y los Estados Unidos contiguos) reciban el mismo color. Dichos requisitos se pueden modelar utilizando los problemas de coloración previa y coloración de listas, aunque es posible que aumenten el número requerido de colores más allá de cuatro. La funcionalidad para estos problemas también se incluye en la biblioteca GCol.
Todo el código fuente utilizado para generar las figuras se puede encontrar aquí. También puede encontrar una versión ampliada de este artículo aquí. Todas las figuras fueron generadas por el autor.