Calculadora de Coloração de Grafos

Calculadora de Coloração de Grafos

A Calculadora de Coloração de Grafos calcula o número cromático χ(G) e uma coloração de vértices válida para qualquer grafo não direcionado. Insira seu grafo como uma lista de arestas ou lista de adjacência e a ferramenta retornará o número mínimo de cores necessárias para que dois vértices adjacentes não compartilhem a mesma cor, junto com uma visualização SVG interativa, um traço animado do algoritmo DSATUR e um detalhamento cor por cor de quais vértices recebem cada cor.

O que é coloração de grafos?

Uma coloração de vértices própria de um grafo G = (V, E) atribui uma cor a cada vértice de modo que cada aresta tenha extremidades de cores diferentes. O número cromático, escrito como χ(G), é o menor número de cores para o qual tal coloração existe. Calcular χ(G) é um problema NP-difícil em geral, mas o problema possui uma bela teoria matemática e muitas aplicações práticas: agendamento de exames, atribuição de frequências de rádio, alocação de registradores em compiladores e o famoso teorema das quatro cores para mapas planares.

Principais teoremas e limites

• Limites triviais: 1 ≤ χ(G) ≤ |V| para qualquer grafo.
• Limite inferior de clique: χ(G) ≥ ω(G), onde ω(G) é o tamanho do maior clique.
• Caracterização bipartida: χ(G) ≤ 2 se, e somente se, G não possui ciclo ímpar (Teorema de König).
• Teorema de Brooks: χ(G) ≤ Δ(G), a menos que G seja um grafo completo ou um ciclo ímpar, caso em que χ(G) = Δ(G) + 1. Aqui Δ(G) é o grau máximo.
• Teorema das quatro cores: Todo grafo planar é 4-colorível.
• Limite superior guloso: Qualquer algoritmo guloso usa no máximo Δ(G) + 1 cores.

Algoritmos usados por esta calculadora

DSATUR (Degree of Saturation)

Introduzido por Daniel Brélaz em 1979, o DSATUR é uma das heurísticas práticas mais fortes para coloração de grafos. Ele escolhe repetidamente o vértice não colorido cujos vizinhos já utilizam o maior número de cores distintas (sua saturação), resolvendo empates pelo grau do vértice, e atribui a ele a menor cor não usada por seus vizinhos. O DSATUR é comprovadamente ótimo em grafos bipartidos e em muitas famílias de grafos estruturados, e produz colorações de alta qualidade em milissegundos em grafos com centenas de vértices.

Welsh-Powell

O algoritmo Welsh-Powell ordena os vértices em ordem decrescente de grau e os colore de forma gulosa. Ele funciona em tempo O(|V|²) e garante no máximo Δ(G) + 1 cores. É extremamente rápido e muitas vezes uma boa primeira aproximação, embora possa ser superado pelo DSATUR em grafos com estrutura local variável.

Guloso (ordem de entrada)

O algoritmo mais simples: percorre os vértices na ordem de entrada e atribui a cada um a menor cor não usada por um vizinho já colorido. O resultado é sensível à ordem de entrada, mas uma ordem aleatória fornece uma base de comparação para heurísticas mais inteligentes.

Backtracking exato

Para grafos pequenos (até cerca de 18 vértices), a calculadora pode encontrar o verdadeiro número cromático tentando k = 2, 3, 4, ... e tentando colorir o grafo com k cores usando backtracking de busca em profundidade. A busca ordena os vértices por grau decrescente e poda os ramos quando nenhuma cor está disponível. Quando o algoritmo exato tem sucesso, o resultado é rotulado como "Exato".

Formatos de entrada

Lista de arestas

Escreva cada aresta como dois rótulos de vértices separados por um hífen, espaço ou seta. Separe as arestas com vírgulas ou quebras de linha. Os rótulos dos vértices podem ser letras, dígitos ou sublinhados. Exemplo:

Lista de adjacência

Escreva cada vértice, dois pontos e a lista de seus vizinhos separada por vírgulas. Exemplo:

Loops próprios são rejeitados porque um vértice não pode receber uma cor diferente de si mesmo. Arestas duplicadas são silenciosamente removidas, e o grafo é tratado como não direcionado.

Como usar esta calculadora

1. Escolha um formato: Alterne entre lista de arestas e lista de adjacência usando os botões de rádio.
2. Insira o grafo: Cole seus dados ou clique em um dos exemplos rápidos (triângulo, completo K₅, roda tipo Petersen, bipartido K₃,₃, agendamento de exames).
3. Escolha um algoritmo: Deixe em Automático para o melhor padrão, ou force Welsh-Powell, guloso, DSATUR ou backtracking exato.
4. Clique em "Colorir o Grafo": O número cromático, uma lista cor por cor, um SVG interativo com nós arrastáveis e um traço animado passo a passo aparecerão abaixo.
5. Explore: Pressione Reproduzir para assistir ao algoritmo colorir os vértices um por um, arraste os nós para reorganizar o layout e use Voltar / Próximo para percorrer o traço manualmente.

Aplicações práticas da coloração de grafos

Agendamento de exames

Considere cada exame como um vértice e desenhe uma aresta entre exames que compartilham pelo menos um aluno. Uma coloração própria com k cores fornece um cronograma com k horários, de modo que nenhum aluno tenha conflitos. O número cromático é o número mínimo de horários necessários.

Atribuição de frequências de rádio

Transmissores dentro da faixa de interferência um do outro devem transmitir em frequências diferentes. O número cromático do grafo de interferência é o número mínimo de frequências necessárias.

Alocação de registradores

Em compiladores, os intervalos de vida das variáveis são vértices; se dois intervalos de vida se sobrepõem no tempo, há uma aresta entre eles. Uma k-coloração atribui variáveis a k registradores de CPU sem colisões.

Coloração de mapas

Países que compartilham uma fronteira devem receber cores diferentes. O teorema das quatro cores (Appel-Haken, 1976) prova que quatro cores sempre bastam para qualquer mapa planar.

Sudoku e quebra-cabeças de restrição

Um Sudoku concluído é uma 9-coloração de um grafo cujos vértices são as 81 células e cujas arestas conectam células na mesma linha, coluna ou bloco 3×3. A coloração de grafos é o núcleo matemático de muitos quebra-cabeças de satisfação de restrições.

Casos especiais interessantes

• Grafo completo K_n: χ(K_n) = n. Cada par de vértices é adjacente, portanto todas as cores devem ser distintas.
• Ciclo C_n: χ(C_n) = 2 se n for par, 3 se n for ímpar.
• Árvore: Qualquer árvore com ≥ 2 vértices possui χ = 2 (árvores são bipartidas).
• Grafo bipartido: χ = 2 se o grafo tiver pelo menos uma aresta.
• Grafo de Petersen: Um famoso grafo 3-regular com χ = 3.
• Roda W_n: Um vértice central unido a um ciclo de n vértices. χ = 3 se n for par, 4 se n for ímpar.

Perguntas frequentes

O que é o número cromático de um grafo?

O número cromático χ(G) é o menor número de cores necessárias para colorir os vértices de um grafo para que dois vértices adjacentes não compartilhem a mesma cor. Grafos bipartidos têm número cromático no máximo 2; qualquer grafo contendo um triângulo tem número cromático pelo menos 3; e pelo teorema de Brooks, o número cromático nunca excede o grau máximo, exceto para grafos completos e ciclos ímpares.

Qual algoritmo esta calculadora utiliza?

Para grafos pequenos, a calculadora executa uma busca exata por backtracking para encontrar o verdadeiro número cromático. Para grafos maiores, utiliza a heurística DSATUR, que colore repetidamente o vértice não colorido com o maior número de vizinhos já coloridos. Você também pode forçar Welsh-Powell ou guloso simples no menu de Algoritmo.

Como devo inserir meu grafo?

Use o modo de lista de arestas para digitar uma aresta por linha, como A-B, ou separadas por vírgulas, como A-B, B-C, C-A. Use o modo de lista de adjacência para escrever cada vértice seguido por dois pontos e seus vizinhos, como A: B, C. Loops próprios são rejeitados porque um vértice não pode ser colorido de forma diferente de si mesmo.

Por que o DSATUR nem sempre encontra o verdadeiro número cromático?

A coloração de grafos é NP-difícil, então nenhum algoritmo rápido conhecido sempre encontra o número mínimo de cores. O DSATUR é uma excelente heurística prática e muitas vezes coincide com o verdadeiro número cromático, mas em grafos adversariais pode usar mais cores do que o necessário. A calculadora relata as cores usadas e um limite inferior do maior clique encontrado, para que você possa avaliar a precisão da resposta.

Qual é um uso real da coloração de grafos?

A coloração de grafos modela o agendamento de exames (cada exame é um vértice, conflitos são arestas, cores são horários), atribuição de frequências de rádio (vértices são transmissores, arestas são interferências), alocação de registradores em compiladores, coloração de mapas, resolução de sudoku e atribuição de tarefas a máquinas sob restrições de conflito.

O número cromático é sempre igual ao maior clique?

Não. O número de clique ω(G) é sempre um limite inferior para o número cromático χ(G), e eles são iguais para grafos perfeitos, como grafos bipartidos, árvores, grafos de intervalo e grafos cordais. Para grafos gerais, χ(G) pode ser estritamente maior que ω(G); o exemplo clássico são os grafos de Mycielski, que não possuem triângulos, mas exigem arbitrariamente muitas cores.

Qual é o maior grafo que esta calculadora pode suportar?

A calculadora suporta até 60 vértices e 600 arestas. Para o algoritmo exato, grafos com mais de aproximadamente 18 vértices podem reverter para o DSATUR porque o backtracking torna-se muito lento. Para uso prático, isso cobre a maioria dos exemplos de sala de aula, problemas de agendamento de exames e aplicações de pequeno a médio porte.

Leitura adicional

• Coloração de grafos — Wikipedia
• Algoritmo DSATUR — Wikipedia
• Polinômio cromático — Wikipedia
• Teorema das quatro cores — Wikipedia
• Teorema de Brooks — Wikipedia