Arestas vs Vértices: Euler e Hamilton

1. As Pontes de Königsberg (Caminho Euleriano)

Leonhard Euler fundou a Teoria dos Grafos em 1736 ao provar que era impossível cruzar as 7 pontes de Königsberg sem repetir nenhuma e voltar ao início.

Definição: Um Ciclo Euleriano percorre todas as arestas do grafo exatamente uma vez e retorna ao início.

Teorema de Euler: Um grafo conexo possui um Ciclo Euleriano se, e somente se, todos os vértices têm Grau Par. (Se houver 0 ou 2 vértices de grau ímpar, existe um Caminho Euleriano, mas não ciclo).

Algoritmo de Hierholzer \(O(E)\)

Para encontrar o ciclo (não apenas dizer que existe): 1. Comece de um vértice qualquer \(v\). 2. Siga um caminho arbitrário até voltar a \(v\) (ou travar), removendo as arestas usadas. 3. Se sobrar arestas no grafo, elas formam sub-ciclos. Funda-os ao ciclo principal.

2. O Caixeiro Viajante (Caminho Hamiltoniano)

William Rowan Hamilton propôs um jogo (“Icosian Game”) em 1857: visitar todas as cidades (vértices) de um dodecaedro exatamente uma vez.

Definição: Um Ciclo Hamiltoniano visita todos os vértices exatamente uma vez e retorna ao início.

O Abismo da Complexidade: Diferente do Euleriano (que olhamos o grau e pronto), saber se um grafo é Hamiltoniano é NP-Completo. Não existe critério simples “se e somente se”.

3. Resolvendo TSP (Traveling Salesman Problem)

O problema do Caixeiro Viajante busca o Ciclo Hamiltoniano de menor peso total. Como é NP-Hard, para \(N\) grande usamos heurísticas (Ant Colony, Genetic) ou aproximações (2-OPT). Para \(N\) pequeno (até 20), podemos usar Programação Dinâmica.

DP com Bitmask (Máscara de Bits)

Estado: dp[mask][u] = menor custo para visitar o conjunto de cidades representado por mask, terminando na cidade u. - mask é um inteiro onde o \(i\)-ésimo bit é 1 se a cidade \(i\) foi visitada.

Transição: Para ir para um estado onde visitamos mask terminando em u, devemos ter vindo de um estado prev_mask (sem \(u\)) terminando num vizinho v. \[ dp[mask][u] = \min_{v \in vizinhos} (dp[mask \setminus \{u\}][v] + peso(v, u)) \]

Complexidade: \(O(2^N \cdot N^2)\). - \(N=20 \implies 2^{20} \approx 10^6 \times 400 \approx 4 \cdot 10^8\) operações. (Limite de 1 a 2 segundos).

Implementação Java (TSP)

public class TSP {
    static final int INF = 100000000;
    
    public static int solveTSP(int[][] dist) {
        int N = dist.length;
        int VISITED_ALL = (1 << N) - 1;
        int[][] dp = new int[1 << N][N];
        
        // Inicializa com Infinito
        for(int[] row : dp) Arrays.fill(row, INF);
        
        // Base: Começar na cidade 0 (mask = 0...01, terminando em 0)
        dp[1][0] = 0;
        
        // Itera por todas as máscaras
        for (int mask = 1; mask < (1 << N); mask++) {
            for (int u = 0; u < N; u++) {
                // Se a cidade u está no set mask
                if ((mask & (1 << u)) != 0) {
                    
                    int prevMask = mask ^ (1 << u);
                    if (prevMask == 0) continue; // Base case
                    
                    for (int v = 0; v < N; v++) {
                        if ((prevMask & (1 << v)) != 0) {
                            dp[mask][u] = Math.min(dp[mask][u], dp[prevMask][v] + dist[v][u]);
                        }
                    }
                }
            }
        }
        
        // Final: conectar o último nó de volta ao 0
        int ans = INF;
        for (int i = 1; i < N; i++) {
            ans = Math.min(ans, dp[VISITED_ALL][i] + dist[i][0]);
        }
        return ans;
    }
}

Observe o salto gigantesco de dificuldade: - Euleriano (\(N=10^6\)): 0.1 segundos. - Hamiltoniano (\(N=25\)): Séculos.

Back to top