Explorador de Coloração de Grafos

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.

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.

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.