O que é coloração de grafos?

É a atribuição de cores (ou quaisquer rótulos) aos vértices de um grafo de modo que dois vértices conectados por uma aresta não compartilhem a mesma cor.

O que é o algoritmo de Welsh-Powell?

É uma heurística de coloração gulosa: ordena os vértices por grau decrescente, depois colore cada um, nessa ordem, com o menor número de cor ainda não usado por um de seus vizinhos já coloridos.

Isso encontra o número mínimo de cores?

Não necessariamente — essa abordagem gulosa dá um limite superior para o número cromático real do grafo. Encontrar o mínimo exato é NP-difícil em geral, então esta calculadora troca garantias de otimalidade por velocidade, como a maioria das ferramentas práticas de coloração de grafos.

O que é o número cromático?

É o menor número de cores necessário para colorir corretamente um grafo — o mínimo teórico que algoritmos gulosos como Welsh-Powell aproximam por cima.

Por que a ordem de coloração importa?

Colorir vértices de alto grau primeiro tende a usar menos cores no total, já que esses vértices têm mais restrições e se beneficiam mais de serem coloridos enquanto ainda há mais opções de cor disponíveis.

O que é o teorema das quatro cores?

Ele afirma que qualquer grafo planar (um que pode ser desenhado sem cruzamentos de arestas) sempre pode ser colorido com no máximo 4 cores — famosamente provado com o auxílio de um computador em 1976, e a origem da intuição de coloração de mapas por trás da coloração de grafos.

Quantos nós esta calculadora consegue processar?

Esta calculadora suporta até 50 nós, mantendo instantâneo o cálculo de coloração gulosa enquanto cobre a grande maioria dos exemplos de grafos inseridos manualmente.

Onde a coloração de grafos é usada na vida real?

É usada para agendamento de exames e reuniões (eventos conflitantes recebem cores/horários diferentes), alocação de registradores em compiladores, atribuição de frequência em redes móveis, e problemas de satisfação de restrições estilo Sudoku.

Calculadora de Coloração de Grafos — Colora um Grafo Sem que Nós Adjacentes Combinem

Nossa Calculadora de Coloração de Grafos atribui uma cor a cada vértice de um grafo de modo que dois vértices diretamente conectados não compartilhem a mesma cor, usando o algoritmo guloso de Welsh-Powell (nós ordenados por grau decrescente), com seu grafo inserido como uma lista de arestas em texto simples (ex. A-B, A-C, B-C).

Resposta rápida

Digite seu grafo como uma lista de arestas para colorir instantaneamente cada vértice de modo que nenhum dois nós conectados compartilhem uma cor, usando o algoritmo guloso de Welsh-Powell.

Arestas (separadas por vírgula)

Digite arestas como NóA-NóB, ex. A-B, A-C, B-C.

Como usar Calculadora de Coloração de Grafos — Algoritmo de Welsh-Powell Online

1
Digite seu grafo como uma lista de arestas separadas por vírgula, ex. A-B, A-C, B-C.
2
Clique em 'Calcular' para colorir cada vértice usando o algoritmo de Welsh-Powell.
3
Revise a cor atribuída a cada nó e o número total de cores usadas.

Por que usar Calculadora de Coloração de Grafos — Algoritmo de Welsh-Powell Online?

A coloração de grafos atribui rótulos ('cores') aos vértices de modo que nenhuma aresta conecte dois vértices da mesma cor — a abstração clássica por trás de problemas de agendamento (dois exames conflitantes não compartilham o mesmo horário) e coloração de mapas (duas regiões adjacentes não compartilham cor). Encontrar o número mínimo real de cores (o número cromático) é NP-difícil em geral, mas a heurística de Welsh-Powell — colorir os vértices em ordem decrescente de grau, sempre escolhendo a menor cor disponível — produz uma coloração boa e rápida que é comprovadamente próxima do ótimo para muitos grafos práticos, exatamente o que esta calculadora computa.

Perguntas frequentes

Ferramentas relacionadas

Calculadora de Árvore Geradora Mínima — Algoritmo de Kruskal Online

Encontre a árvore geradora mínima de um grafo ponderado usando o algoritmo de Kruskal. Calculadora gratuita com uma entrada simples de lista de arestas e detecção de ciclos via union-find.

Validador de Sequência de Graus de Grafo — Teorema de Erdős–Gallai Online

Verifique se uma sequência de números é uma sequência de graus válida (gráfica) usando o teorema de Erdős–Gallai. Calculadora gratuita com verificação passo a passo.

Calculadora de Matriz de Adjacência — Construa uma Matriz de Grafo Online

Construa e exiba a matriz de adjacência de um grafo a partir de uma entrada simples de lista de arestas, junto com sua sequência de graus. Calculadora gratuita, ponderada ou não ponderada.

Solucionador do Problema do Casamento Estável — Algoritmo de Gale-Shapley Online

Encontre uma correspondência estável entre dois grupos de mesmo tamanho a partir de suas listas de preferências usando o algoritmo de Gale-Shapley. Calculadora gratuita, resultados estáveis garantidos.