← Computação

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.

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

  1. 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.

    Abrir este problema na ferramenta

    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)≤χ(G)≤Δ(G)+1:Petersen has ω=2, Δ=3 ⟹ 2≤χ≤4\omega(G)\le\chi(G)\le\Delta(G)+1:\quad \text{Petersen has }\omega=2,\ \Delta=3\ \Longrightarrow\ 2\le\chi\le4

    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\text{girth}=5\ \Longrightarrow\ \text{no triangle}\ \Longrightarrow\ \omega=2,\ \text{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 ⟹ χ≥3\text{bipartite}\iff\text{no odd cycle};\ \text{the outer 5-cycle is odd}\ \Longrightarrow\ \chi\ge3

    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\text{a 3-colouring exists}\ \Longrightarrow\ \chi=3,\ \text{strictly above the clique bound } \omega=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 χ≤3 for a connected non-complete graph|V|=10,\ |E|=15,\ \Delta=3:\ \text{Brooks' theorem gives }\chi\le3\ \text{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\chi(\text{Petersen})=3>\omega=2:\ \text{the clique bound is not tight}
  2. 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.

    Abrir este problema na ferramenta

    1. Conte as arestas em vez de confiar na imagem: todos os pares de quatro vértices estão unidos, e existem seis pares.

      K4: ∣V∣=4, ∣E∣=(42)=6, every pair adjacentK_4:\ |V|=4,\ |E|=\binom{4}{2}=6,\ \text{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 ⟹ χ≥4\text{all four vertices are mutually adjacent}\ \Longrightarrow\ \omega=4\ \Longrightarrow\ \chi\ge4

    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 ⟹ χ(Kn)=n\text{four colours suffice trivially}\ \Longrightarrow\ \chi(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\text{here }\omega=\chi=4:\ \text{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\Delta+1=4\ \text{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.

    χ(K4)=ω(K4)=Δ+1=4\chi(K_4)=\omega(K_4)=\Delta+1=4
Referências (2)

· Verificado com fontes publicadas. Correções bem-vindas.