Coloración de Grafos
Colorea un grafo con el menor número de colores posible
Acerca de esta calculadora
La Calculadora de Coloración de Grafos encuentra el número cromático χ(G) — el menor número de colores necesarios para colorear los vértices de un grafo de modo que ninguna arista una dos vértices del mismo color — y muestra una coloración óptima. Introduce el número de vértices y una lista de aristas; calcula χ de forma exacta con una búsqueda de ramificación y poda, informa del grado máximo Δ y del clique más grande ω (una cota inferior de χ), señala los grafos bipartitos y completos, y dibuja el grafo coloreado. Útil para la planificación, la asignación de registros, la coloración de mapas y el estudio de los números cromáticos.
Cómo colorear un grafo
- Introduce el número de vértices; se numeran de 1 a n.
- Enumera las aristas como pares como 1-2, 2-3 — un par por conexión.
- Lee el número cromático χ(G) y el color asignado a cada vértice.
- Compara χ con el clique más grande ω para ver por qué se necesitan esos colores, o carga un ejemplo para explorar.
Ejemplos comunes
- Un triángulo (K₃) necesita 3 colores — cada par de sus vértices es adyacente.
- Los ciclos pares son bipartitos y solo necesitan 2 colores; los ciclos impares como C₅ necesitan 3.
- El grafo completo Kₙ necesita exactamente n colores.
- Un clique más grande de tamaño ω fuerza al menos ω colores, por lo que χ(G) ≥ ω.
- El grafo de Grötzsch necesita 4 colores pero no contiene ningún triángulo, así que χ puede superar el número de clique.
Preguntas frecuentes
¿Qué es el número cromático?
El número cromático χ(G) es el menor número de colores necesarios para colorear los vértices de un grafo de modo que ninguna arista conecte dos vértices del mismo color.
¿Cómo se encuentra el número mínimo de colores?
Como el grafo es pequeño, la calculadora busca de forma exacta: prueba con 1 color, luego con 2, y así sucesivamente, devolviendo el primer número para el que existe una coloración propia. Ese número está garantizado que es el mínimo verdadero.
¿Qué son el grado máximo y el clique más grande?
El grado máximo Δ es el mayor número de aristas que concurren en un solo vértice. El clique más grande ω es el conjunto más grande de vértices que son todos mutuamente adyacentes; como todos deben diferir, χ(G) es al menos ω.
¿Por qué un grafo sin triángulos puede necesitar aun así muchos colores?
Un clique grande fuerza muchos colores, pero no es la única razón. Los ciclos impares y grafos como el de Grötzsch necesitan colores adicionales incluso sin ningún triángulo, así que χ(G) puede ser mayor que el número de clique.
¿Hay un límite en el tamaño del grafo?
Sí. La coloración exacta de grafos es computacionalmente difícil, así que la calculadora limita el grafo a 12 vértices para mantener los resultados instantáneos y rigurosos.