Coloração de Grafos
Colora um grafo com o menor número possível de cores
Sobre esta calculadora
A Calculadora de Coloração de Grafos encontra o número cromático χ(G) — o menor número de cores necessárias para colorir os vértices de um grafo de modo que nenhuma aresta una dois vértices da mesma cor — e mostra uma coloração ótima. Insira o número de vértices e uma lista de arestas; ela calcula χ exatamente com uma busca branch-and-bound, informa o grau máximo Δ e o maior clique ω (um limite inferior para χ), sinaliza grafos bipartidos e completos e desenha o grafo colorido. Útil para escalonamento, alocação de registradores, coloração de mapas e estudo de números cromáticos.
Como colorir um grafo
- Insira o número de vértices; eles são numerados de 1 a n.
- Liste as arestas como pares como 1-2, 2-3 — um par por conexão.
- Leia o número cromático χ(G) e a cor atribuída a cada vértice.
- Compare χ com o maior clique ω para ver por que são necessárias tantas cores, ou carregue um exemplo predefinido para explorar.
Exemplos comuns
- Um triângulo (K₃) precisa de 3 cores — cada par de seus vértices é adjacente.
- Ciclos pares são bipartidos e precisam de apenas 2 cores; ciclos ímpares como C₅ precisam de 3.
- O grafo completo Kₙ precisa de exatamente n cores.
- Um maior clique de tamanho ω força pelo menos ω cores, então χ(G) ≥ ω.
- O grafo de Grötzsch precisa de 4 cores mas não contém nenhum triângulo, então χ pode exceder o número de clique.
Perguntas frequentes
O que é o número cromático?
O número cromático χ(G) é o menor número de cores necessárias para colorir os vértices de um grafo de modo que nenhuma aresta conecte dois vértices da mesma cor.
Como o número mínimo de cores é encontrado?
Como o grafo é pequeno, a calculadora busca exatamente: ela tenta 1 cor, depois 2 e assim por diante, retornando a primeira contagem para a qual existe uma coloração própria. Essa contagem é garantidamente o mínimo verdadeiro.
O que são o grau máximo e o maior clique?
O grau máximo Δ é o maior número de arestas que se encontram em um único vértice. O maior clique ω é o maior conjunto de vértices que são todos mutuamente adjacentes; como todos devem diferir, χ(G) é pelo menos ω.
Por que um grafo sem triângulos ainda pode precisar de muitas cores?
Um grande clique força muitas cores, mas não é o único motivo. Ciclos ímpares e grafos como o grafo de Grötzsch precisam de cores extras mesmo sem nenhum triângulo, então χ(G) pode ser maior que o número de clique.
Existe um limite para o tamanho do grafo?
Sim. A coloração exata de grafos é computacionalmente difícil, então a calculadora limita o grafo a 12 vértices para manter os resultados instantâneos e rigorosos.