Coloração de Grafos

1. O Mapa Mundi

Pegue um mapa político. O Brasil não pode ter a mesma cor que a Argentina, nem que o Paraguai. Quantas cores no mínimo precisamos para pintar o mapa inteiro sem conflitos? Este é o problema da Coloração de Grafos.

Definição: Uma \(k\)-coloração é uma atribuição de cores \(c: V \to \{1 \dots k\}\) tal que para toda aresta \((u, v)\), \(c(u) \neq c(v)\). O menor \(k\) possível é o Número Cromático \(\chi(G)\).

2. Um Problema Difícil (NP-Hard)

Descobrir se um grafo é 2-colorível é fácil (Bipartido, \(O(V+E)\)). Descobrir se é 3-colorível… já é NP-Completo! Isso significa que não conhecemos (e provavelmente não existe) um algoritmo rápido para encontrar o número cromático mínimo de um grafo qualquer.

Aplicações Reais: 1. Alocação de Registradores em Compiladores: Variáveis vivas simultaneamente não podem compartilhar o mesmo registrador da CPU (são vizinhos no grafo de interferência). As “cores” são os registradores (eax, ebx, etc). 2. Sudoku: É um problema de coloração com 9 cores num grafo de 81 vértices. 3. Agendamento de Horários: Provas que ocorrem ao mesmo tempo com alunos em comum não podem ser na mesma sala/horário.

3. Heurística Gulosa (Welsh-Powell)

Como o ótimo é difícil, usamos heurísticas que dão uma solução “boa o suficiente” bem rápido. A estratégia Welsh-Powell tenta pintar primeiro os vértices mais difíceis (maior grau).

Algoritmo: 1. Ordene os vértices por Grau Decrescente. 2. Itere pelos vértices ordenados: - Para o vértice \(u\), verifique as cores dos vizinhos já pintados. - Atribua a menor cor disponível (0, 1, 2…) que não conflite.

Implementação Java

import java.util.*;

public class GraphColoring {
    
    // Representa um par (Grau, ID) para ordenação
    static class Vertex implements Comparable<Vertex> {
        int id, degree;
        public Vertex(int i, int d) { id=i; degree=d; }
        public int compareTo(Vertex o) { return o.degree - this.degree; } // Decrescente
    }

    public static int greedyColoring(int V, List<List<Integer>> adj) {
        int[] result = new int[V];
        Arrays.fill(result, -1);
        
        // 1. Calcular graus e ordenar
        List<Vertex> vertices = new ArrayList<>();
        for(int i=0; i<V; i++) {
            vertices.add(new Vertex(i, adj.get(i).size()));
        }
        Collections.sort(vertices);
        
        // Array para marcar cores usadas pelos vizinhos
        boolean[] available = new boolean[V];
        
        for (Vertex vObj : vertices) {
            int u = vObj.id;
            
            // Reseta disponibilidade
            Arrays.fill(available, true);
            
            // Marca cores indisponíveis (vizinhos)
            for (int viz : adj.get(u)) {
                if (result[viz] != -1) {
                    available[result[viz]] = false;
                }
            }
            
            // Acha a primeira livre
            int color;
            for (color = 0; color < V; color++) {
                if (available[color]) break;
            }
            
            result[u] = color;
        }
        
        // Conta quantas cores foram usadas (maior índice + 1)
        int maxColor = 0;
        for(int c : result) maxColor = Math.max(maxColor, c);
        return maxColor + 1;
    }
}

4. Backtracking (Solução Exata para Grafos Pequenos)

Se precisamos garantidamente do mínimo (e \(V\) é pequeno, tipo \(< 20\)), usamos força bruta inteligente (Backtracking).

tryColor(u, cor): 1. Tenta pintar \(u\) com a cor atual. 2. Se válido, chama recursivamente para o próximo vértice. 3. Se falhar, tenta a próxima cor. 4. Se nenhuma cor servir, volta (backtrack).

5. Teorema das Quatro Cores

Foi provado em 1976 (usando computador!) que todo grafo planar (que pode ser desenhado no papel sem arestas se cruzarem) é 4-colorível. Ou seja, para qualquer mapa mundi real ou imaginário, 4 lápis de cor são suficientes.

Back to top