Explorador de Coloração de Grafos

Arraste vértices, desenhe arestas e colora o grafo manualmente ou com um algoritmo guloso — veja como o limite inferior por clique revela quantas cores você realmente precisa.

Exemplo resolvido — Explorador de Coloração de Grafos

Vértices	3
Arestas	3
Cores usadas	0
Conflitos	0

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

quantas cores você realmente precisa? 🖖

O número cromático χ(G) é a quantidade mínima de cores necessária para que nenhuma aresta ligue dois vértices da mesma cor. Determiná-lo exatamente é NP-difícil — a melhor garantia geral fica entre um limite inferior por clique (toda clique de tamanho k exige pelo menos k cores) e um limite superior guloso (a coloração de Welsh-Powell, por grau decrescente, nunca usa mais de Δ+1 cores, onde Δ é o grau máximo). Para grafos planares — aqueles que podem ser desenhados sem arestas se cruzando — o teorema das quatro cores garante que 4 cores sempre bastam; ele foi provado pela primeira vez por computador em 1976 e continua sendo um dos poucos teoremas importantes que exigem verificação exaustiva de casos por computador. A coloração de grafos está por trás de problemas reais de alocação: alocação de registradores em compiladores, montagem de horários de provas e atribuição de frequências de rádio se reduzem todos à coloração de um grafo de conflitos.

vizinhos devem diferir — esse é o jogo todo 🖖

A coloração de grafos se resume a uma regra: nenhuma aresta pode ligar dois vértices da mesma cor, e você quer usar o menor número possível de cores. Essa única condição decide tudo. Um teste útil: todo ciclo de comprimento par se colore com 2 cores, mas todo ciclo de comprimento ímpar precisa de 3 — então um triângulo (o menor ciclo ímpar) nunca pode ser colorido com 2. Construa ambos na ferramenta e observe o número de conflitos.

a coloração gulosa pode falhar espetacularmente 🖖

Colorir os vértices um a um, escolhendo sempre a menor cor livre, parece seguro, mas a ordem importa enormemente. Numa família chamada grafos coroa — 2n vértices que precisam de apenas 2 cores — uma ordem maliciosa força o método guloso a usar n cores. Seu pior caso não tem limite, e é exatamente por isso que a coloração automática da ferramenta ordena os vértices por grau decrescente (Welsh-Powell) para evitar tais armadilhas.

Problemas resolvidos na íntegra

O verdadeiro número cromático do grafo de Petersen 5 passos
O grafo de Petersen tem 10 vértices, 15 arestas e nenhum triângulo. O painel indica, portanto, χ ≥ 2. Encontre o verdadeiro número cromático. Este é o estado Grafo de Petersen.
1. Dois limites vêm sem custos para qualquer grafo: precisa de pelo menos tantas cores quanto a sua maior clique, e nunca mais do que uma acima do seu grau máximo.
  
  $ω (G) \leq χ (G) \leq Δ (G) + 1 : Petersen has ω = 2, Δ = 3 ⟹ 2 \leq χ \leq 4$
2. A cintura de Petersen é 5, pelo que não existe qualquer triângulo nele e o limite por clique reduz-se ao trivial 2. Esse é o número que o painel apresenta.
  
  $girth = 5 ⟹ no triangle ⟹ ω = 2, yet the graph is not bipartite$
3. Duas cores só são possíveis se o grafo for bipartido, e bipartido significa a ausência de ciclos ímpares. O pentágono exterior é um 5-ciclo, pelo que duas cores estão fora de questão.
  
  $bipartite ⟺ no odd cycle; the outer 5-cycle is odd ⟹ χ \geq 3$
4. É possível usar três cores, e apresentar uma disposição basta para provar a cota superior. Percorra o pentágono exterior e pinte os vértices, pela ordem, com as cores 1, 2, 1, 2, 3. Depois, seguindo a mesma ordem e associando cada vértice interior ao vértice exterior ligado pelo respetivo raio, pinte os cinco vértices interiores com 2, 1, 3, 3, 2. Verifique as quinze arestas: os dois extremos de cada uma têm sempre cores diferentes.
  
  $a 3-colouring exists ⟹ χ = 3, strictly above the clique bound ω = 2$
5. O teorema de Brooks afirma o mesmo a partir de cima: um grafo conexo que não seja nem completo nem um ciclo ímpar precisa no máximo de Δ cores, e Δ é 3 aqui.
  
  $∣ V ∣ = 10, ∣ E ∣ = 15, Δ = 3 : Brooks’ theorem gives χ \leq 3 for a connected non-complete graph$
Resposta

3, que está estritamente acima do limite que o painel consegue provar. A maior clique em Petersen é uma única aresta, pelo que o limite por clique fornece apenas χ ≥ 2, errando por um. A diferença importa mais do que parece: Petersen é o contraexemplo padrão à intuição de que a dificuldade da coloração advém das cliques, e existem grafos sem triângulos que necessitam de quatro cores, cinco, qualquer número que se deseje — a construção de Mycielski produz-os por encomenda. Assim, o número de clique é um limite inferior que pode estar arbitrariamente distante, razão pela qual determinar o número cromático é NP-difícil, ao passo que encontrar um triângulo não o é. O que fixa Petersen em exatamente 3 é um ciclo ímpar para o limite inferior e o teorema de Brooks para o superior.

$χ (Petersen) = 3 > ω = 2 : the clique bound is not tight$
Comparar limites para χ no grafo completo K4 5 passos
Agora K₄ — quatro vértices, com todas as seis arestas presentes. Determine χ e compare os limites com o resultado no grafo de Petersen. Este é o estado K4 Completo.
1. Conte as arestas em vez de confiar na imagem: todos os pares de quatro vértices estão unidos, e existem seis pares.
  
  $K_{4} : ∣ V ∣ = 4, ∣ E ∣ = (2 4) = 6, every pair adjacent$
2. Cada vértice é adjacente a todos os outros, pelo que nenhuns dois podem partilhar uma cor. Esse é um limite inferior de 4 e não necessita de qualquer argumento além da definição.
  
  $all four vertices are mutually adjacent ⟹ ω = 4 ⟹ χ \geq 4$
3. Quatro cores são obviamente suficientes, pelo que o limite é atingido. O mesmo raciocínio fornece χ(Kₙ) = n para todo o n, o que faz dos grafos completos o caso simples.
  
  $four colours suffice trivially ⟹ χ (K_{n}) = n$
4. Coloque os dois grafos lado a lado. A mesma questão, os mesmos dois limites, e a diferença entre eles é todo o tema em estudo.
  
  $here ω = χ = 4 : the bound is tight, and Petersen showed it need not be$
5. Note-se onde o teorema de Brooks se situa aqui. O seu limite de Δ = 3 estaria errado para K₄, razão pela qual os grafos completos são expressamente excluídos dele.
  
  $Δ + 1 = 4 as well — Brooks’ theorem excludes complete graphs for exactly this reason$
Resposta

4, e aqui todos os limites são exatos ao mesmo tempo. O número de clique é 4 porque todo o grafo é uma clique, Δ + 1 é 4 porque cada vértice se conecta aos outros três, e a resposta verdadeira fica encurralada entre eles sem para onde ir. Esse é o caso sobre o qual as pessoas constroem a sua intuição, e é exatamente o caso que o teorema de Brooks exclui — o seu limite de Δ aplica-se a qualquer grafo conexo exceto grafos completos e ciclos ímpares, sendo estes dois problemas a razão de ambas as exceções. Petersen e K₄ marcam os dois extremos: um em que o limite por clique falha por um, outro em que não pode falhar de todo.

$χ (K_{4}) = ω (K_{4}) = Δ + 1 = 4$

Referências (2)

Insight block 1 — the four colour theorem, and the computer proof it needed: K. Appel and W. Haken, "Every planar map is four colorable. Part I: Discharging." Illinois Journal of Mathematics 21(3), 429–490, 1977.
And the descending-degree ordering the auto-colour button uses: D. J. A. Welsh and M. B. Powell, "An upper bound for the chromatic number of a graph and its application to timetabling problems." The Computer Journal 10(1), 85–86, 1967.

Pela equipa 42Math · Atualizado 2026-06-16

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Explorador de Coloração de Grafos

quantas cores você realmente precisa? 🖖

vizinhos devem diferir — esse é o jogo todo 🖖

a coloração gulosa pode falhar espetacularmente 🖖

Problemas de exemplo