Calculadora de Coloração de Grafos

Calculadoras relacionadas

• Analisador de Grafos de Rede
• Simulador de Autômatos Celulares
• Explorador de Teoria dos Nós
• Criador de Máquinas de Estados Finitos

O que é coloração de grafos?

A coloração de grafos consiste em atribuir cores, números ou rótulos às partes de um grafo seguindo uma regra sobre conflitos. Na coloração de vértices, as partes coloridas são os vértices, e a regra usual é simples: vértices conectados por uma aresta não devem ter a mesma cor.

Um grafo normalmente é escrito como \(G=(V,E)\), em que \(V\) é o conjunto de vértices e \(E\) é o conjunto de arestas. Uma coloração atribui uma cor a cada vértice:

Uma coloração é própria quando cada aresta conecta vértices de cores diferentes:

O número cromático de um grafo, escrito como \(\chi(G)\), é o menor número de cores necessário para uma coloração própria dos vértices:

A coloração de grafos é importante porque muitos problemas reais são, na verdade, problemas de conflitos. Duas provas com alunos em comum não podem acontecer ao mesmo tempo. Dois trabalhos que precisam da mesma máquina não podem ser executados no mesmo horário. Dois transmissores de rádio muito próximos talvez não possam usar a mesma frequência. Em cada caso, as cores podem representar horários, máquinas, frequências, grupos ou outros recursos compartilhados.

---

Por que a coloração de grafos é importante

A coloração de grafos transforma um problema complexo de distribuição com conflitos em um modelo visual e matemático. Em vez de testar manualmente todos os horários ou atribuições possíveis, você pode desenhar um grafo:

• Cada item se torna um vértice.
• Cada conflito se torna uma aresta.
• Cada cor se torna um grupo ou horário.
• Uma atribuição válida não tem nenhuma aresta conectando dois vértices da mesma cor.

Isso é útil em salas de aula, elaboração de horários, distribuição de recursos, planejamento de redes, alocação de registradores em computação e muitos exemplos didáticos de teoria dos grafos. O principal benefício é a clareza: depois que os conflitos são representados por arestas, a coloração mostra quais itens podem compartilhar um grupo com segurança e quais precisam ser separados.

O objetivo costuma ser usar o menor número possível de cores. Menos cores podem significar menos horários, lotes, rótulos ou recursos. No entanto, encontrar o mínimo verdadeiro pode ser difícil em grafos maiores; por isso, ferramentas práticas frequentemente comparam a busca exata em grafos pequenos com métodos heurísticos, que são mais rápidos, mas não garantem um resultado mínimo.

---

Termos importantes

• Vértice: Um ponto ou item do grafo. Em um modelo de horários, um vértice pode representar uma aula, um trabalho, uma tarefa ou um evento.
• Aresta: Uma conexão entre dois vértices. Na coloração de grafos, uma aresta geralmente significa que os dois vértices estão em conflito e não devem compartilhar uma cor.
• Vértices adjacentes: Dois vértices unidos por uma aresta.
• Grau: O número de arestas conectadas a um vértice. Um vértice de alto grau tem muitas restrições.
• Grupo de cor: Todos os vértices atribuídos à mesma cor. Em uma coloração válida, um grupo de cor não contém nenhum par adjacente.
• Coloração própria: Uma coloração sem pares adjacentes da mesma cor.
• Conflito: Uma aresta cujas extremidades têm a mesma cor.
• Número cromático: O número mínimo de cores necessário para uma coloração própria.
• Heurística: Um método prático que tenta encontrar uma boa coloração, mas pode não encontrar o mínimo.
• Busca exata: Um método que prova o número mínimo de cores para o grafo pesquisado.
• Grau de saturação: Em uma coloração no estilo DSATUR, o número de cores diferentes já usadas pelos vizinhos coloridos de um vértice.

---

Como funciona a coloração de grafos

Uma coloração de grafos começa pelas arestas. As arestas definem quais pares não podem compartilhar uma cor. A distância visual não importa: dois vértices podem ser desenhados longe um do outro e ainda assim estar em conflito se uma aresta os unir, enquanto dois vértices podem ser desenhados próximos, mas ser compatíveis se nenhuma aresta os unir.

Para uma coloração proposta \(c\), a contagem de conflitos pode ser escrita como:

Uma coloração própria tem:

Um algoritmo de coloração tenta atribuir cores de modo que essa contagem de conflitos seja zero, de preferência usando o menor número possível de cores.

Coloração gulosa simples

Um método guloso simples percorre os vértices em uma ordem escolhida. Para cada vértice, ele verifica as cores já usadas pelos vizinhos coloridos e atribui a menor cor ainda disponível.

Isso pode funcionar bem, mas o resultado depende muito da ordem dos vértices. Às vezes, o mesmo grafo pode receber números diferentes de cores se os vértices forem percorridos em outra sequência.

Coloração de Welsh-Powell

A ideia de Welsh-Powell é um método guloso ordenado pelo grau. Primeiro, ele ordena os vértices do maior para o menor grau e depois aplica a coloração gulosa. O motivo é prático: vértices com muitas arestas costumam ser mais difíceis de posicionar, então colori-los primeiro pode reduzir conflitos posteriores.

Welsh-Powell ainda é uma heurística. Ele pode produzir um bom limite superior para o número cromático, mas nem sempre prova que o número de cores é mínimo.

Coloração DSATUR

O DSATUR usa uma regra mais adaptativa. Em vez de depender apenas da ordem original dos graus, ele escolhe repetidamente um vértice não colorido com o maior grau de saturação. Em termos simples, ele se concentra nos vértices cujas cores vizinhas já criam as restrições mais rígidas.

Uma regra de escolha típica do DSATUR é:

1. Escolha um vértice não colorido com o maior grau de saturação.
2. Em caso de empate, escolha o vértice empatado com o maior grau.
3. Teste as cores permitidas e continue a busca.

Aqui, o branch-and-bound do DSATUR recebe um orçamento determinístico de 200.000 nós para a prova. Se não conseguir terminar, a calculadora informa limites inferior e superior certificados em vez de afirmar um número cromático exato.

---

Exemplos práticos de coloração de grafos

Exemplo 1: Um horário simples com conflitos

Suponha que quatro atividades sejam representadas por vértices:

• \(A\) = Cálculo
• \(B\) = Física
• \(C\) = História
• \(D\) = Economia

Suponha que os conflitos sejam:

$$ E=\{\{A,B\},\{A,C\},\{B,D\}\} $$

Uma coloração válida é:

• Cor 1: \(A\), \(D\)
• Cor 2: \(B\), \(C\)

Isso funciona porque \(A\) não está conectado a \(D\), e \(B\) não está conectado a \(C\). Os grupos de cor podem ser interpretados como dois horários.

---

Exemplo 2: Um grafo completo

Em um grafo completo \(K_n\), cada vértice é adjacente a todos os outros vértices. Isso significa que dois vértices quaisquer não podem compartilhar uma cor.

Para \(K_5\), os cinco vértices são mutuamente adjacentes, portanto o número cromático é:

$$ \chi(K_5)=5 $$

Este é um lembrete útil de que uma contagem alta de cores não é necessariamente um problema do método. Alguns grafos realmente exigem muitas cores porque cada item está em conflito com muitos outros.

---

Exemplo 3: Ciclos pares e ímpares

Um grafo ciclo conecta os vértices em um circuito fechado. Ciclos pares podem ser coloridos alternando duas cores:

$$ \chi(C_6)=2 $$

Ciclos ímpares não podem ser completados com apenas duas cores alternadas, porque a aresta final conectaria dois vértices da mesma cor. Um ciclo ímpar como \(C_5\) precisa de três cores:

$$ \chi(C_5)=3 $$

Este é um caso-limite comum: um grafo pode parecer quase bicolorível, mas uma aresta extra ou um ciclo ímpar pode exigir uma cor adicional.

---

Exemplo 4: Uma coloração manual com conflito

Suponha que os dois vértices adjacentes \(X\) e \(Y\) recebam a Cor 1. A contagem de cores pode parecer baixa, mas a coloração não é válida porque:

$$ \{X,Y\}\in E \quad\text{and}\quad c(X)=c(Y) $$

Essa aresta é um conflito. Uma interpretação válida exige zero conflitos, e não apenas um número pequeno de cores.

---

Como interpretar o resultado

O resultado mais importante não é apenas o número de cores usadas. É a combinação da contagem de cores, da contagem de conflitos e do tipo de resultado.

Um resultado de zero conflitos significa que cada aresta conecta vértices de cores diferentes. Em uma interpretação de horários, cada grupo de cor pode ser tratado como um horário em que os vértices listados são mutuamente compatíveis.

Um resultado de conflitos diferentes de zero significa que pelo menos um par adjacente compartilha uma cor. A coloração não deve ser tratada como um horário ou uma atribuição válida até que esses conflitos sejam corrigidos.

Uma contagem baixa de cores geralmente significa que o grafo pode ser agrupado com eficiência, mas isso só é útil se a contagem de conflitos for zero. Uma coloração manual com poucas cores e conflitos não é uma coloração própria.

Uma contagem alta de cores pode significar que o grafo tem muitas restrições. Grafos completos, grafos densos e grafos com grandes cliques naturalmente exigem mais cores.

Um número cromático exato significa que a minimalidade foi provada. Um intervalo certificado significa que o valor verdadeiro está entre os limites exibidos. Um limite superior heurístico é uma coloração própria cuja contagem de cores pode ser maior que o mínimo. As atribuições manuais são informadas separadamente como válidas ou inválidas.

Uma atribuição manual descreve as cores escolhidas pelo usuário. Ela é uma avaliação dessa atribuição, não uma otimização automática.

---

Erros e equívocos comuns

Supor que todo resultado guloso seja o número cromático. Métodos gulosos podem encontrar boas colorações rapidamente, mas nem sempre encontram o mínimo. Um resultado guloso normalmente deve ser interpretado como um limite superior ou uma estimativa, a menos que uma busca exata o confirme.

Ignorar conflitos porque a contagem de cores é baixa. Um resultado com três cores e conflitos não é melhor que um resultado com quatro cores e zero conflitos. Uma coloração própria exige que todas as arestas sejam respeitadas.

Usar o modo de pintura esperando otimização. A coloração manual serve para testar uma atribuição escolhida. Ela pode criar conflitos intencionalmente, que então são contados e destacados.

Confundir proximidade visual com adjacência. Somente as arestas definem conflitos. Dois vértices que parecem próximos na tela são compatíveis se nenhuma aresta os conecta.

Esquecer que os rótulos não são a mesma coisa que a estrutura do grafo. O rótulo de um vértice ajuda a ler o grafo, mas as arestas determinam o problema de coloração. Rótulos exibidos duplicados podem causar confusão mesmo que o grafo trate os vértices como itens internos separados.

Esperar tipos de grafos não compatíveis. A coloração padrão de vértices aqui se baseia em um grafo simples não direcionado. Arestas direcionadas, arestas ponderadas, hiperarestas, laços e arestas paralelas exigem modelos diferentes.

Considerar horários válidos sem verificar os conflitos. Grupos de cor podem representar horários somente quando a contagem de conflitos é zero.

---

Quando usar a coloração de grafos

Use a coloração de grafos quando precisar dividir itens em grupos compatíveis respeitando conflitos entre pares.

Os casos de uso comuns incluem:

• Agendar aulas, provas, reuniões ou trabalhos que não podem se sobrepor.
• Atribuir recursos limitados a tarefas com conflitos.
• Modelar restrições de compatibilidade entre máquinas e trabalhos.
• Ensinar conceitos de teoria dos grafos, como número cromático, grafos bipartidos, ciclos, grafos completos e algoritmos gulosos.
• Comparar a busca exata com métodos heurísticos de coloração.
• Testar se um agrupamento manual cria conflitos.

A coloração de grafos é mais útil quando a pergunta principal é: “Quais itens podem compartilhar um grupo e de quantos grupos precisamos?”

---

Limitações e pontos importantes

A coloração de grafos é um modelo. Sua utilidade depende de o grafo representar com precisão os conflitos reais.

O cálculo pressupõe um grafo simples não direcionado. Isso significa que uma aresta não tem direção, arestas duplicadas não são tratadas como restrições separadas e laços não fazem parte do modelo compatível.

A exatidão depende da conclusão da prova dentro de 200.000 nós de busca, e não de um limite oculto para o tamanho do grafo. Se o orçamento se esgotar, o intervalo certificado continua sendo útil, enquanto os resultados heurísticos são limites superiores e nunca provam a minimalidade.

Os métodos disponíveis não respondem diretamente a todas as perguntas possíveis sobre coloração de grafos. Por exemplo, um objetivo fixo como “Este grafo pode ser colorido com exatamente \(k\) cores?” pode exigir um teste separado de colorabilidade com \(k\) cores.

Os grupos de cor são grupos matemáticos, não necessariamente amostras visuais distintas. Se forem usados mais índices de cor do que o número de amostras diferentes exibidas, as cores visuais podem se repetir mesmo que os números de cor subjacentes sejam diferentes.

Os layouts manuais servem para facilitar a leitura. Arrastar vértices pode tornar o grafo mais fácil de examinar, mas não o altera, a menos que arestas ou vértices sejam modificados.

Para decisões importantes de planejamento, engenharia, operações, finanças, questões jurídicas ou segurança, trate o resultado como um auxílio de modelagem. Verifique novamente o grafo informado, confirme que todas as restrições reais estão representadas e consulte um profissional qualificado quando a decisão tiver consequências sérias.

---

Como usar esta calculadora

1. Escolha um grafo predefinido para começar com um exemplo pronto, como um ciclo, grafo completo, grafo bipartido, grafo roda ou grafo de horários.
2. Escolha um algoritmo de coloração ou mude para o modo de pintura para testar sua própria coloração.
3. Adicione um vértice informando um rótulo. Se o rótulo ficar em branco, será usado um rótulo automático, como V6.
4. No modo de arestas, escolha duas extremidades ou clique em dois vértices do grafo para adicionar ou remover uma aresta.
5. No modo de pintura, clique em um vértice para alternar entre as cores e testar uma atribuição manual.
6. Revise o resumo do resultado, a contagem de vértices, a contagem de arestas, as cores usadas, a contagem de conflitos, a legenda, a tabela de comparação e a tabela de horários.
7. Procure as arestas de conflito destacadas. Uma coloração válida tem zero conflitos.
8. Arraste os vértices para facilitar a leitura do grafo.
9. Use a opção de baixar o grafo para salvar uma imagem do grafo atual quando precisar de uma cópia.

---

Perguntas frequentes

---

Fontes e referências

Livros

1. Reinhard Diestel. Graph Theory. 6ª edição, Springer Nature, 2025. Capítulo 5, “Colouring”. Prévia no Google Books.
2. Douglas B. West. Introduction to Graph Theory. 2ª edição, Prentice Hall/Pearson, 2001. Seções sobre coloração de grafos e algoritmos de grafos. ISBN 0-13-014400-2.
3. Oscar Levin. Discrete Mathematics: An Open Introduction. 4ª edição, 2024. Seção 2.5, “Coloring”. Seção do livro aberto.

Fontes on-line e originais dos algoritmos

1. D. J. A. Welsh e M. B. Powell. “An upper bound for the chromatic number of a graph and its application to timetabling problems.” The Computer Journal, volume 10, edição 1, 1967, páginas 85–86. DOI: 10.1093/comjnl/10.1.85.
2. Daniel Brélaz. “New methods to color the vertices of a graph.” Communications of the ACM, volume 22, edição 4, 1979, páginas 251–256. DOI: 10.1145/359094.359101.
3. JGraphT. “SaturationDegreeColoring.” Documentação do JGraphT, consultada em 28 de junho de 2026. Página da documentação.