Calculadora de Coloración de Grafos

Calculadora de Coloración de Grafos

La Calculadora de Coloración de Grafos calcula el número cromático χ(G) y una coloración de vértices válida para cualquier grafo no dirigido. Ingresa tu grafo como una lista de aristas o una lista de adyacencia y la herramienta devolverá el número mínimo de colores necesarios para que no haya dos vértices adyacentes que compartan color, junto con una visualización SVG interactiva, una traza animada de DSATUR y un desglose color por color de qué vértices reciben qué color.

¿Qué es la coloración de grafos?

Una coloración propia de vértices de un grafo G = (V, E) asigna un color a cada vértice de modo que cada arista tenga extremos de diferentes colores. El número cromático, escrito como χ(G), es el número más pequeño de colores para el cual existe tal coloración. Calcular χ(G) es un problema NP-duro en general, pero el problema tiene una hermosa teoría matemática y muchas aplicaciones prácticas: programación de exámenes, asignación de radiofrecuencias, asignación de registros en compiladores y el famoso teorema de los cuatro colores para mapas planos.

Teoremas y límites clave

• Límites triviales: 1 ≤ χ(G) ≤ |V| para cualquier grafo.
• Límite inferior de clique: χ(G) ≥ ω(G), donde ω(G) es el tamaño del clique más grande.
• Caracterización bipartita: χ(G) ≤ 2 si y solo si G no tiene ciclos impares (König).
• Teorema de Brooks: χ(G) ≤ Δ(G), a menos que G sea un grafo completo o un ciclo impar, en cuyo caso χ(G) = Δ(G) + 1. Aquí Δ(G) es el grado máximo.
• Teorema de los cuatro colores: Todo grafo plano es 4-coloreable.
• Límite superior voraz: Cualquier algoritmo voraz utiliza como máximo Δ(G) + 1 colores.

Algoritmos utilizados por esta calculadora

DSATUR (Grado de Saturación)

Introducido por Daniel Brélaz en 1979, DSATUR es una de las heurísticas prácticas más potentes para la coloración de grafos. Selecciona repetidamente el vértice no coloreado cuyos vecinos ya utilizan la mayor cantidad de colores distintos (su saturación), rompiendo empates por el grado del vértice, y le asigna el color más pequeño no utilizado por sus vecinos. DSATUR es demostrablemente óptimo en grafos bipartitos y en muchas familias de grafos estructurados, y produce coloraciones de alta calidad en milisegundos en grafos con cientos de vértices.

Welsh-Powell

El algoritmo de Welsh-Powell ordena los vértices en orden descendente de grado y luego los colorea de forma voraz. Se ejecuta en tiempo O(|V|²) y garantiza como máximo Δ(G) + 1 colores. Es extremadamente rápido y suele ser una buena primera aproximación, aunque puede ser superado por DSATUR en grafos con estructura local variable.

Voraz (orden de entrada)

El algoritmo más simple: recorre los vértices en el orden de entrada y asigna a cada uno el color más pequeño no utilizado por un vecino ya coloreado. El resultado es sensible al orden de entrada, pero un orden aleatorio proporciona una base de referencia que puedes comparar con las heurísticas más inteligentes.

Retroceso exacto (backtracking)

Para grafos pequeños (hasta unos 18 vértices), la calculadora puede encontrar el número cromático real probando k = 2, 3, 4, ... e intentando k-colorear el grafo con retroceso de búsqueda en profundidad. La búsqueda ordena los vértices por grado descendente y poda la búsqueda cuando no hay colores disponibles. Cuando el algoritmo exacto tiene éxito, el resultado se etiqueta como "Exacto".

Formatos de entrada

Lista de aristas

Escribe cada arista como dos etiquetas de vértices separadas por un guion, espacio o flecha. Separa las aristas con comas o saltos de línea. Las etiquetas de los vértices pueden ser letras, dígitos o guiones bajos. Ejemplo:

Lista de adyacencia

Escribe cada vértice, dos puntos y la lista de sus vecinos separada por comas. Ejemplo:

Se rechazan los bucles infinitos porque a un vértice no se le puede asignar un color diferente al de sí mismo. Las aristas duplicadas se eliminan silenciosamente y el grafo se trata como no dirigido.

Cómo usar esta calculadora

1. Elige un formato: Alterna entre lista de aristas y lista de adyacencia con los botones de radio.
2. Ingresa el grafo: Pega tus datos o haz clic en uno de los ejemplos rápidos (triángulo, completo K₅, rueda tipo Petersen, bipartito K₃,₃, programación de exámenes).
3. Elige un algoritmo: Deja en Automático para el mejor valor predeterminado, o fuerza Welsh-Powell, voraz, DSATUR o retroceso exacto.
4. Haz clic en "Colorear el Grafo": Debajo aparecerán el número cromático, una lista de colores, un SVG interactivo con nodos arrastrables y una traza animada paso a paso.
5. Explora: Presiona Reproducir para ver cómo el algoritmo colorea los vértices uno a uno, arrastra los nodos para reorganizar el diseño y usa Atrás / Siguiente para avanzar manualmente por la traza.

Aplicaciones prácticas de la coloración de grafos

Programación de exámenes

Deja que cada examen sea un vértice y dibuja una arista entre los exámenes que comparten al menos un estudiante. Una coloración propia con k colores proporciona un calendario con k franjas horarias de modo que ningún estudiante tenga un conflicto. El número cromático es el número mínimo de franjas.

Asignación de radiofrecuencias

Los transmisores que están dentro del rango de interferencia entre sí deben emitir en frecuencias diferentes. El número cromático del grafo de interferencia es el número mínimo de frecuencias necesarias.

Asignación de registros

En los compiladores, los rangos de vida de las variables son vértices; que dos rangos de vida se solapen en el tiempo significa que hay una arista entre ellos. Una k-coloración asigna variables a k registros de CPU sin colisiones.

Coloración de mapas

Los países que comparten frontera deben recibir colores diferentes. El teorema de los cuatro colores (Appel-Haken, 1976) demuestra que cuatro colores siempre son suficientes para cualquier mapa plano.

Sudoku y acertijos de restricciones

Un Sudoku completado es una 9-coloración de un grafo cuyos vértices son las 81 celdas y cuyas aristas conectan celdas en la misma fila, columna o cuadro de 3×3. La coloración de grafos es el núcleo matemático de muchos rompecabezas de satisfacción de restricciones.

Casos especiales interesantes

• Grafo completo K_n: χ(K_n) = n. Cada par de vértices es adyacente, por lo que todos los colores deben ser distintos.
• Ciclo C_n: χ(C_n) = 2 si n es par, 3 si n es impar.
• Árbol: Cualquier árbol con ≥ 2 vértices tiene χ = 2 (los árboles son bipartitos).
• Grafo bipartito: χ = 2 si el grafo tiene al menos una arista.
• Grafo de Petersen: Un famoso grafo 3-regular con χ = 3.
• Rueda W_n: Un vértice central unido a un n-ciclo. χ = 3 si n es par, 4 si n es impar.

Preguntas frecuentes

¿Qué es el número cromático de un grafo?

El número cromático χ(G) es el número mínimo de colores necesarios para colorear los vértices de un grafo de modo que no haya dos vértices adyacentes que compartan el mismo color. Los grafos bipartitos tienen un número cromático de como máximo 2; cualquier grafo que contenga un triángulo tiene un número cromático de al menos 3; y por el teorema de Brooks el número cromático nunca excede el grado máximo, excepto para grafos completos y ciclos impares.

¿Qué algoritmo utiliza esta calculadora?

Para grafos pequeños, la calculadora ejecuta una búsqueda de retroceso exacta para encontrar el número cromático real. Para grafos más grandes utiliza la heurística DSATUR, que colorea repetidamente el vértice no coloreado con más vecinos ya coloreados. También puedes forzar Welsh-Powell o voraz simple desde el menú desplegable de Algoritmo.

¿Cómo debo ingresar mi grafo?

Usa el modo de lista de aristas para escribir una arista por línea como A-B, o separadas por comas como A-B, B-C, C-A. Usa el modo de lista de adyacencia para escribir cada vértice seguido de dos puntos y sus vecinos, como A: B, C. Se rechazan los bucles infinitos porque un vértice no puede colorearse de forma diferente a sí mismo.

¿Por qué DSATUR no siempre encuentra el número cromático real?

La coloración de grafos es NP-duro, por lo que ningún algoritmo rápido conocido encuentra siempre el número mínimo de colores. DSATUR es una excelente heurística práctica y a menudo coincide con el número cromático real, pero en grafos adversos puede usar más colores de los necesarios. La calculadora informa tanto los colores usados como un límite inferior del clique más grande encontrado, para que puedas juzgar la precisión del resultado.

¿Cuál es un uso real de la coloración de grafos?

La coloración de grafos modela la programación de exámenes (cada examen es un vértice, los conflictos son aristas, los colores son franjas horarias), la asignación de radiofrecuencias (los vértices son transmisores, las aristas son interferencias), la asignación de registros en compiladores, la coloración de mapas, la resolución de sudokus y la asignación de trabajos a máquinas bajo restricciones de conflicto.

¿Es el número cromático siempre igual al clique más grande?

No. El número de clique ω(G) es siempre un límite inferior para el número cromático χ(G), y son iguales para grafos perfectos como grafos bipartitos, árboles, grafos de intervalo y grafos cordales. Para grafos generales χ(G) puede ser estrictamente mayor que ω(G); el ejemplo clásico son los grafos de Mycielski, que no tienen triángulos pero necesitan arbitrariamente muchos colores.

¿Cuál es el grafo más grande que puede manejar esta calculadora?

La calculadora admite hasta 60 vértices y 600 aristas. Para el algoritmo exacto, los grafos con más de unos 18 vértices pueden recurrir a DSATUR porque el retroceso se vuelve demasiado lento. Para uso práctico, esto cubre la mayoría de los ejemplos escolares, problemas de programación de exámenes y aplicaciones pequeñas y medianas.

Lectura adicional

• Coloración de grafos — Wikipedia
• Algoritmo DSATUR — Wikipedia
• Polinomio cromático — Wikipedia
• Teorema de los cuatro colores — Wikipedia
• Teorema de Brooks — Wikipedia