Grafos Eulerianos e Hamiltonianos

Em Grafos: Uma Linguagem para Modelar Conexões, vimos que o problema das Pontes de Königsberg se resume a um argumento de paridade: as quatro regiões da cidade — Altstadt, Kneiphof, Lomse e Vorstadt — têm graus 3, 5, 3 e 3, respectivamente. Toda região que não é ponto de partida nem de chegada de um passeio precisa ter um número par de pontes; como as quatro regiões de Königsberg têm grau ímpar, o passeio completo é impossível.

Esse argumento informal esconde dois conceitos que merecem nome próprio e demonstração rigorosa. Primeiro: o que significa exatamente “percorrer cada aresta uma única vez”? Um grafo que admite esse tipo de percurso é chamado de grafo euleriano. Segundo: e se, em vez de percorrer todas as pontes, quiséssemos apenas visitar cada região uma única vez? Essa pergunta, parecida na superfície, é na verdade um problema completamente diferente — e muito mais difícil — que dá origem aos grafos hamiltonianos.

Neste artigo, formalizamos os dois conceitos, demonstramos o Teorema de Euler — que caracteriza completamente os grafos eulerianos — e exploramos por que a pergunta análoga sobre vértices resiste a uma caracterização simples até hoje, culminando no notório Problema do Caixeiro Viajante.

Por que grafos eulerianos e hamiltonianos importam?

#

Saber se um grafo admite esses dois tipos de percurso não é curiosidade histórica — é um problema prático recorrente em ciência da computação e engenharia:

• Roteamento urbano: encontrar uma rota que passe por cada rua de um bairro exatamente uma vez — coleta de lixo, entrega de correspondência, remoção de neve, inspeção de tubulações — é um problema euleriano, conhecido como Problema do Carteiro Chinês.
• Bioinformática: a montagem de um genoma a partir de fragmentos curtos de DNA é modelada como um trajeto euleriano em um grafo de De Bruijn — a estratégia usada pelos sequenciadores modernos de alto rendimento.
• Logística e entregas: decidir a ordem de visita a um conjunto de endereços minimizando a distância percorrida é o Problema do Caixeiro Viajante — uma pergunta hamiltoniana.
• Projeto de circuitos: planejar o caminho de uma furadeira ou sonda de solda que precisa visitar cada ponto de um circuito impresso exatamente uma vez.
• Escalonamento de tarefas: sequenciar operações em uma máquina que precisa passar por cada configuração do sistema exatamente uma vez.

A boa notícia é que o problema euleriano tem solução simples e eficiente, como veremos a seguir. A má notícia é que o problema hamiltoniano — parecido na formulação — está entre os mais difíceis que a ciência da computação conhece.

Dois problemas, um mesmo grafo

#

Para apreciar a diferença entre os dois problemas, considere sete cidades \(a, b, c, d, e, f, g\) ligadas por estradas, representadas pelo grafo abaixo.

Problema do explorador. Um explorador quer percorrer cada estrada exatamente uma vez, partindo de \(a\) e retornando a \(a\) no final. Um percurso que resolve o problema é \(a \to b \to c \to d \to e \to f \to b \to g \to c \to e \to g \to f \to a\). Repare que o explorador passa por \(b\), \(c\), \(e\), \(f\) e \(g\) mais de uma vez — o que importa é que cada uma das 12 estradas (arestas) do grafo seja usada exatamente uma vez.

Problema do viajante. Um viajante quer visitar cada cidade exatamente uma vez, partindo de \(a\) e retornando a \(a\) no final. Um percurso que resolve esse problema é \(a \to b \to c \to d \to e \to g \to f \to a\). Aqui a lógica se inverte: cada cidade (vértice) aparece uma única vez, mas nem toda estrada (aresta) precisa ser usada — a diagonal \(bg\), por exemplo, fica de fora.

O primeiro é o problema euleriano; o segundo, o hamiltoniano. Vamos tratá-los separadamente, começando pelo mais simples.

Grafos Eulerianos

#

Teorema de Euler

#

O argumento informal que demos na abertura — cada passagem por uma região consome um par de pontes, então só início e fim podem ter grau ímpar — é, na verdade, a metade fácil do teorema a seguir. Vamos enunciá-lo e demonstrá-lo com precisão.

Prova da condição necessária (euleriano → graus pares):

Seja \(C\) um circuito euleriano de \(G\). Cada vez que \(C\) passa por um vértice \(v\), ele “entra” por uma aresta e “sai” por outra — consumindo duas unidades do grau de \(v\) (o vértice inicial conta a saída no começo e a entrada no final, já que o circuito é fechado). Como cada aresta do grafo é usada exatamente uma vez, o grau de \(v\) é igual a duas vezes o número de passagens de \(C\) por \(v\). Portanto, \(d(v)\) é par para todo vértice \(v\) de \(G\), que é o que queríamos demonstrar. \(\blacksquare\)

Prova da condição suficiente (graus pares → euleriano): por indução forte no número \(m\) de arestas. Suponha que todo grafo conexo com graus pares, pelo menos uma aresta e menos de \(m\) arestas seja euleriano, e seja \(G\) um grafo conexo com \(m\) arestas (\(m \geq 1\)) e todos os graus pares.

Passo 1: \(G\) tem um ciclo. Como \(G\) é conexo e tem arestas, todo vértice tem grau pelo menos 1; como os graus são pares, todo vértice tem grau pelo menos 2. Tome um caminho \(P = v_0, v_1, \ldots, v_k\) de comprimento máximo em \(G\). O vértice \(v_k\) tem pelo menos dois vizinhos: um é \(v_{k-1}\); o outro, \(w\), precisa estar em \(P\) — se não estivesse, dava para estender \(P\) até \(w\), e \(P\) não seria máximo. Se \(w = v_i\), então \(v_i, v_{i+1}, \ldots, v_k, v_i\) é um ciclo \(C\).

Passo 2: tirar o ciclo. Seja \(H\) o grafo obtido removendo de \(G\) as arestas de \(C\), sem remover vértices. Cada vértice de \(C\) perde exatamente 2 do seu grau, e os demais não perdem nada: todos os graus de \(H\) continuam pares. \(H\) pode ser desconexo, mas cada componente conexo de \(H\) é um grafo conexo, com graus pares e menos de \(m\) arestas. Pela hipótese de indução, cada componente que tem arestas admite um circuito euleriano.

Passo 3: costurar os circuitos. Todo componente de \(H\) com arestas toca \(C\). De fato, como \(G\) é conexo, há um caminho em \(G\) de um vértice desse componente até \(C\); a primeira aresta desse caminho que não está em \(H\) é uma aresta de \(C\), e o vértice em que ela começa pertence ao componente e a \(C\). Agora percorra \(C\): ao chegar pela primeira vez a um vértice de \(C\) em que ainda há um componente de \(H\) não percorrido, faça um desvio pelo circuito euleriano desse componente — que começa e termina nesse vértice — e depois siga por \(C\). O resultado é um trajeto fechado que usa cada aresta de \(C\) e cada aresta de \(H\) exatamente uma vez, isto é, cada aresta de \(G\) exatamente uma vez. (Não é preciso caso base separado: se \(H\) não tiver arestas, o circuito é o próprio \(C\).)

Portanto, \(G\) é euleriano; junto com a condição necessária, um grafo conexo é euleriano se e somente se todos os seus vértices têm grau par, que é o que queríamos demonstrar. \(\blacksquare\)

Esse teorema é notável por dar uma forma eficiente de decidir se um grafo é euleriano: basta verificar a paridade do grau de cada vértice, sem precisar procurar o circuito de fato.

Exemplo: quando os grafos deixam de ser eulerianos

#

Considere os quatro grafos abaixo, todos sobre subconjuntos dos vértices \(a, b, c, d, e, f, g\) — o primeiro reaproveita o próprio grafo de sete cidades que vimos na motivação. A figura a seguir mostra os quatro lado a lado.

import networkx as nx

G1 = nx.Graph([("a", "b"), ("a", "f"), ("b", "c"), ("b", "f"), ("b", "g"),
               ("c", "d"), ("c", "e"), ("c", "g"), ("d", "e"), ("e", "f"),
               ("e", "g"), ("f", "g")])
G2 = nx.Graph([("b", "c"), ("b", "g"), ("c", "g"), ("e", "f"), ("e", "g"), ("f", "g")])
G3 = nx.Graph([("b", "c"), ("c", "e"), ("e", "f"), ("f", "b"),
               ("b", "g"), ("c", "g"), ("e", "g"), ("f", "g")])
G4 = nx.Graph([("b", "c"), ("c", "e"), ("e", "f"), ("f", "b"), ("a", "b"),
               ("b", "g"), ("c", "g"), ("e", "g"), ("f", "g"), ("c", "d")])

for nome, G in [("G1", G1), ("G2", G2), ("G3", G3), ("G4", G4)]:
    print(f"{nome} é euleriano? {nx.is_eulerian(G)}")

print("Circuito euleriano de G1:", list(nx.eulerian_circuit(G1, source="a")))

G1 é euleriano? True
G2 é euleriano? True
G3 é euleriano? False
G4 é euleriano? False
Circuito euleriano de G1: [('a', 'f'), ('f', 'g'), ('g', 'e'), ('e', 'c'), ('c', 'g'), ('g', 'b'), ('b', 'f'), ('f', 'e'), ('e', 'd'), ('d', 'c'), ('c', 'b'), ('b', 'a')]

Trajetos eulerianos abertos

#

Nem todo grafo com um trajeto euleriano precisa ser fechado. Relaxando a exigência de retornar ao ponto de partida, chegamos a uma versão aberta do teorema — exatamente a generalização que prometemos em Grafos: Uma Linguagem para Modelar Conexões, o artigo que introduziu o problema das Pontes de Königsberg e deu origem a toda a teoria dos grafos.

Vale relembrar rapidamente o problema original, mesmo para quem não leu o primeiro artigo da série: quatro regiões de Königsberg — Altstadt, Kneiphof, Lomse e Vorstadt —, ligadas por sete pontes sobre o rio Pregel, e a pergunta era se dava para cruzar cada ponte exatamente uma vez. O mapa abaixo mostra a disposição das pontes:

Euler abstraiu esse mapa no grafo abaixo — cada região virou um vértice, cada ponte uma aresta, e as arestas duplas entre A–B e B–D representam os pares de pontes que existiam entre essas regiões.

Grafos Hamiltonianos

#

Hamilton e o jogo Icosiano

#

O nome “hamiltoniano” vem de Sir William Rowan Hamilton (1805-1865), que popularizou o problema com o Jogo Icosiano (Icosian Game), um quebra-cabeça comercializado em 1857. O tabuleiro representa o grafo de um dodecaedro — 20 vértices, 30 arestas, cada vértice com exatamente 3 vizinhos — e o desafio é: dada uma sequência inicial de cinco vértices consecutivos de um percurso, completar um ciclo que visite os 15 vértices restantes exatamente uma vez e retorne ao início. A figura abaixo mostra o grafo desenhado como um pentágono externo, uma faixa de 10 vértices e um pentágono interno — o arranjo clássico usado no tabuleiro original —, com os 5 vértices iniciais do desafio em verde e um ciclo hamiltoniano completo destacado em laranja.

Apesar do nome remeter ao icosaedro, o grafo do jogo é o do dodecaedro — Hamilton batizou seu sistema de cálculo algébrico de “cálculo icosiano” por outros motivos matemáticos, e o jogo herdou essa referência no nome, ainda que jogue-se sobre o grafo do sólido dual.

Nem toda pergunta tem resposta fácil

#

Diferentemente do problema euleriano, decidir se um grafo é hamiltoniano parece, à primeira vista, uma pergunta parecida — mas não se conhece nenhuma caracterização completa e eficiente como a do Teorema de Euler. Decidir se um grafo arbitrário é hamiltoniano é, de fato, um problema NP-completo (a sigla, do inglês Nondeterministic Polynomial time, identifica a classe dos problemas de decisão mais difíceis entre os verificáveis em tempo polinomial): não se conhece algoritmo eficiente que resolva o caso geral. O que existem são condições parciais: suficientes, mas não necessárias.

Uma observação simples ajuda a construir intuição: quanto mais arestas um grafo tem, maior a chance de ele ser hamiltoniano. O ciclo \(C_n\) (com \(n\) vértices) já é, trivialmente, hamiltoniano — ele é o próprio ciclo hamiltoniano. Se acrescentarmos arestas a \(C_n\), o grafo resultante continua contendo esse mesmo ciclo como subgrafo, logo continua hamiltoniano. No limite, o grafo completo \(K_n\) — que tem todas as arestas possíveis — também é hamiltoniano. A sequência de figuras abaixo ilustra essa progressão.

Essa observação não é uma prova — é apenas uma intuição de que grafos “densos” (com muitas arestas) tendem a ser hamiltonianos. Mas ela motiva exatamente os dois teoremas de condição suficiente mais importantes da teoria, publicados com poucos anos de diferença.

Condições Suficientes: Dirac e Ore

#

Note que o Teorema de Dirac é um caso particular do de Ore: se \(d(v) \geq n/2\) e \(d(w) \geq n/2\) para quaisquer \(v, w\), então \(d(v) + d(w) \geq n\) mesmo quando \(v\) e \(w\) não são adjacentes. Ore é, portanto, uma condição estritamente mais abrangente. Os dois grafos a seguir mostram um caso em que Dirac já resolve e outro em que só Ore resolve.

O Problema do Caixeiro Viajante (TSP)

#

O Problema do Caixeiro Viajante (do inglês Travelling Salesman Problem, TSP) é uma das questões mais famosas — e desafiadoras — da matemática e da ciência da computação:

Um pouco de história

#

O problema é mais antigo do que parece. Um manual alemão de 1832 para caixeiros-viajantes já mencionava a importância de planejar bem a rota, sem tratamento matemático. A matemática entrou em cena ainda no século XIX, com William Rowan Hamilton e Thomas Kirkman, que estudaram ciclos que visitam cada vértice de um grafo — o mesmo conceito que motivou o Jogo Icosiano que vimos antes. A forma geral do problema apareceu nos anos 1930: o matemático austríaco Karl Menger, então em Viena e depois em Harvard, estudou-o sob o nome de Botenproblem (“problema do mensageiro”). O nome em inglês, “traveling salesman problem”, aparece pela primeira vez em um relatório de 1949 da matemática Julia Robinson para a RAND Corporation — instituição que, nos anos seguintes, ofereceu prêmios para estimular pesquisas sobre o tema.

O primeiro grande avanço prático veio em 1954: George Dantzig, Delbert Fulkerson e Selmer Johnson resolveram de forma ótima uma instância com 49 cidades usando um método de planos de corte — a semente das técnicas de otimização combinatória usadas até hoje.

Um exemplo pequeno

#

Considere cinco cidades \(A, B, C, D, E\) ligadas pelas estradas e distâncias do grafo abaixo.

Dois ciclos hamiltonianos possíveis:

• \(C_1: A \to B \to C \to D \to E \to A\), com custo \(5+2+4+3+4 = 18\)
• \(C_2: A \to C \to B \to D \to E \to A\), com custo \(3+2+2+3+4 = 14\)

Testando todos os ciclos hamiltonianos possíveis desse grafo, \(C_2\) é de fato o de menor custo — a solução ótima deste pequeno exemplo.

Por que é difícil

#

Com \(n\) cidades, partindo de uma cidade fixa, o número de ciclos hamiltonianos que podemos formar — contando os dois sentidos de percurso como diferentes — é \((n-1)!\):

• 10 cidades: \(9! = 362.880\) percursos
• 20 cidades: \(19! \approx 1{,}22 \times 10^{17}\) percursos
• 50 cidades: verificar por força bruta levaria mais tempo do que a idade do universo

(Como percorrer um ciclo em um sentido ou no outro dá exatamente o mesmo custo total, alguns autores dividem esse número por 2 para contar apenas ciclos distintos. A ordem de grandeza do problema não muda.)

A animação abaixo mostra a força bruta testando exaustivamente os ciclos de um TSP com 7 cidades até achar o ótimo:

Vale precisar melhor o que exatamente é difícil aqui. A versão de decisão do problema — “existe um ciclo hamiltoniano de custo no máximo \(k\)?” — é NP-completa. A versão de otimização — “qual é o ciclo de menor custo?”, que é a que realmente nos interessa — é NP-difícil: pelo menos tão difícil quanto qualquer problema em NP. Em 1972, Richard Karp demonstrou que decidir se um grafo tem um ciclo hamiltoniano — o problema que estudamos neste mesmo artigo — é NP-completo. Daí sai a dificuldade do TSP: dando peso 1 às arestas de um grafo com \(n\) vértices e peso 2 aos pares de vértices que não são arestas, o grafo tem um ciclo hamiltoniano se e somente se o TSP tem um ciclo de custo \(n\) — mais um elo entre os dois temas centrais deste texto.

Algoritmos exatos: além da força bruta

#

Força bruta não é a única opção exata. O algoritmo de Held-Karp (1962) usa programação dinâmica para resolver o TSP em tempo \(O(n^2 2^n)\) — ainda exponencial, mas muito melhor que \(O(n!)\):

A ideia: para cada subconjunto \(S\) de cidades já visitadas e cada cidade \(j \in S\), guardamos o menor custo para chegar a \(j\) tendo visitado exatamente as cidades de \(S\). Cada novo subconjunto se constrói a partir de subconjuntos menores, evitando recalcular o mesmo caminho parcial várias vezes — a marca registrada de qualquer programação dinâmica.

O código abaixo implementa Held-Karp para o nosso exemplo das cinco cidades (usando uma máscara de bits (bitmask) para representar subconjuntos de cidades: o bit \(j\) de um inteiro indica se a cidade \(j\) já foi visitada):

import math
from itertools import combinations

cidades = ["A", "B", "C", "D", "E"]
INF = math.inf
dist = {
    ("A", "B"): 5, ("A", "C"): 3, ("A", "D"): 6, ("A", "E"): 4,
    ("B", "C"): 2, ("B", "D"): 2,
    ("C", "D"): 4,
    ("D", "E"): 3,
}

def d(i, j):
    if i == j:
        return 0
    return dist.get((i, j), dist.get((j, i), INF))

n = len(cidades)
# dp[(subset, j)] = menor custo para visitar exatamente `subset`
# (bitmask sobre as cidades 1..n-1), terminando na cidade j
dp = {}
for j in range(1, n):
    dp[(1 << j, j)] = d(cidades[0], cidades[j])

for tamanho in range(2, n):
    for subset in combinations(range(1, n), tamanho):
        bits = sum(1 << b for b in subset)
        for j in subset:
            bits_sem_j = bits & ~(1 << j)
            dp[(bits, j)] = min(
                dp[(bits_sem_j, k)] + d(cidades[k], cidades[j])
                for k in subset if k != j
            )

todas = sum(1 << b for b in range(1, n))
custo_otimo = min(dp[(todas, j)] + d(cidades[j], cidades[0]) for j in range(1, n))
print(f"Custo do ciclo ótimo: {custo_otimo}")

Custo do ciclo ótimo: 14

O resultado bate exatamente com o \(C_2\) que encontramos por inspeção. A diferença é que Held-Karp encontra esse valor de forma sistemática, sem precisar enumerar os ciclos manualmente — e continua funcionando (em princípio) para instâncias maiores, embora \(2^n\) ainda cresça rápido demais para ser prático além de umas 20-30 cidades.

Para instâncias maiores, o método de escolha é o branch-and-bound combinado com técnicas de programação linear (branch-and-cut), que descarta ramos inteiros da árvore de busca sempre que consegue provar que não levam a uma solução melhor que a já conhecida. A animação abaixo mostra o mesmo TSP de 7 cidades resolvido dessa forma, explorando muito menos ramos que a força bruta:

É essa família de técnicas — refinada ao longo de décadas no software Concorde TSP Solver — que permitiu resolver otimamente instâncias reais enormes: 15.112 cidades da Alemanha em 2001, 24.978 cidades da Suécia em 2004, e um recorde de 85.900 pontos (um problema de perfuração de placas de circuito impresso) em 2006, usando mais de 136 anos-CPU de processamento.

Heurísticas: soluções boas, rapidamente

#

Quando o exato é caro demais, heurísticas encontram soluções boas — não necessariamente ótimas — em tempo muito menor.

A mais simples é o vizinho mais próximo (nearest neighbour): comece em uma cidade qualquer e, a cada passo, vá para a cidade não visitada mais próxima. Veja abaixo essa heurística em ação num TSP com 7 cidades:

import math

cidades = ["A", "B", "C", "D", "E"]
INF = math.inf
dist = {
    ("A", "B"): 5, ("A", "C"): 3, ("A", "D"): 6, ("A", "E"): 4,
    ("B", "C"): 2, ("B", "D"): 2,
    ("C", "D"): 4,
    ("D", "E"): 3,
}


def d(i, j):
    if i == j:
        return 0
    return dist.get((i, j), dist.get((j, i), INF))


def vizinho_mais_proximo(inicio):
    nao_visitadas = set(cidades) - {inicio}
    tour = [inicio]
    atual = inicio
    custo_total = 0
    while nao_visitadas:
        proxima = min(nao_visitadas, key=lambda c: d(atual, c))
        custo_total += d(atual, proxima)
        tour.append(proxima)
        nao_visitadas.remove(proxima)
        atual = proxima
    custo_total += d(atual, inicio)
    tour.append(inicio)
    return tour, custo_total

for cidade in cidades:
    tour, custo = vizinho_mais_proximo(cidade)
    print(f"{' -> '.join(tour)}: custo {custo}")

A -> C -> B -> D -> E -> A: custo 14
B -> D -> E -> A -> C -> B: custo 14
C -> B -> D -> E -> A -> C: custo 14
D -> B -> C -> A -> E -> D: custo 14
E -> D -> B -> C -> A -> E: custo 14

Nesse exemplo pequeno, o vizinho mais próximo encontra o ótimo (14) a partir de qualquer cidade inicial — mas isso é uma coincidência do exemplo reduzido, não uma garantia geral. Em instâncias maiores, essa heurística tipicamente produz tours cerca de 25% mais longos que o ótimo, e no pior caso pode ficar arbitrariamente pior. Ainda assim, sua simplicidade a torna um bom ponto de partida para heurísticas mais refinadas.

Uma dessas melhorias é o 2-opt: dado um tour qualquer, procure duas arestas que, se trocadas de lugar (desfazendo um cruzamento), reduzam a distância total. Repita até não encontrar mais melhorias. A figura abaixo mostra uma dessas trocas:

Aplicado repetidamente sobre uma solução inicial (como a do vizinho mais próximo), o 2-opt costuma melhorar bastante o tour: em instâncias euclidianas, dá em média soluções cerca de 5% melhores que as do algoritmo de Christofides-Serdyukov, que veremos a seguir — e variantes mais sofisticadas, como o 3-opt e a heurística de Lin-Kernighan, chegam ainda mais perto do ótimo.

O algoritmo de Christofides-Serdyukov: eulerianos e hamiltonianos juntos

#

Nenhuma heurística ilustra melhor a conexão entre os dois temas deste artigo do que o algoritmo de Christofides-Serdyukov (1976). Ele funciona em grafos métricos — onde as distâncias satisfazem a desigualdade triangular — e garante um tour com custo no máximo 1,5 vezes o ótimo. Por décadas, ninguém conseguiu uma garantia melhor. Em 2011 veio uma melhora minúscula, mas só para um caso particular, o TSP em grafos (em que a distância entre duas cidades é o número de arestas do caminho mais curto num grafo sem pesos); para o TSP métrico geral, o fator 1,5 só foi batido em 2020, por Anna Karlin, Nathan Klein e Shayan Oveis Gharan, com um algoritmo aleatorizado de fator \(1{,}5 - 10^{-36}\) (veja o verbete Christofides algorithm).

Os passos do algoritmo usam, em sequência, uma árvore geradora mínima, um emparelhamento de peso mínimo e — aqui está a conexão — um circuito euleriano:

1. Árvore geradora mínima. Construa a árvore geradora mínima do grafo ponderado.

2. Emparelhamento nos vértices de grau ímpar. Na árvore geradora mínima, identifique os vértices de grau ímpar. Pelo Lema do Aperto de Mãos, esse conjunto tem sempre um número par de vértices — o que torna possível emparelhá-los. Calcule o emparelhamento de peso mínimo entre eles e acrescente essas arestas à árvore. A figura abaixo ilustra esse passo:

   

3. Circuito euleriano. Cada vértice de grau ímpar identificado no passo anterior tinha seu grau aumentado em exatamente 1 pelo emparelhamento — logo, todo vértice do multigrafo resultante (árvore mais emparelhamento) passa a ter grau par. Pelo Teorema de Euler que demonstramos neste artigo, na versão para multigrafos, esse multigrafo é euleriano: encontre um circuito euleriano nele.

4. Atalho para um ciclo hamiltoniano. Percorra o circuito euleriano na ordem encontrada, mas pule qualquer cidade já visitada, seguindo direto para a próxima cidade nova. Como o grafo é métrico, “cortar caminho” dessa forma nunca aumenta o custo total (desigualdade triangular). O resultado é um ciclo hamiltoniano — a resposta do algoritmo. A figura abaixo mostra esse atalho sendo aplicado:

   

import networkx as nx

G_completo = nx.Graph()
G_completo.add_weighted_edges_from([
    ("A", "B", 5), ("A", "C", 3), ("A", "D", 6), ("A", "E", 4),
    ("B", "C", 2), ("B", "D", 2), ("B", "E", 5),
    ("C", "D", 4), ("C", "E", 7),
    ("D", "E", 3),
])

tour = nx.approximation.christofides(G_completo, weight="weight")
custo = sum(G_completo[tour[i]][tour[i + 1]]["weight"] for i in range(len(tour) - 1))
print("Tour:", " -> ".join(tour))
print("Custo:", custo)

Tour: A -> E -> D -> B -> C -> A
Custo: 14

Em outras palavras: Christofides-Serdyukov constrói deliberadamente um grafo euleriano só para poder “atalhá-lo” até um grafo hamiltoniano — usando os dois teoremas que são o assunto deste artigo como ferramentas de um algoritmo de aproximação real, ainda usado hoje.

Outras metaheurísticas populares — algoritmos genéticos, simulated annealing, busca tabu, e otimização por colônia de formigas (que simula formigas depositando feromônio nos caminhos mais curtos) — também produzem bons resultados práticos, mas sem a garantia matemática de 1,5x que Christofides-Serdyukov oferece para grafos métricos.

Casos especiais

#

Nem todo TSP é igualmente difícil na prática:

• TSP métrico: quando as distâncias satisfazem a desigualdade triangular (\(d(u,w) \leq d(u,v) + d(v,w)\) para quaisquer \(u, v, w\)) — o caso mais comum em aplicações reais, já que distâncias geográficas se comportam assim. É o que permite a garantia de 1,5x de Christofides-Serdyukov.
• TSP euclidiano: quando as cidades são pontos do plano e a distância é a distância euclidiana usual. Continua sendo NP-difícil, mas admite um PTAS (esquema de aproximação em tempo polinomial) descoberto por Sanjeev Arora e Joseph Mitchell — trabalho premiado com o Prêmio Gödel de 2010 — que se aproxima do ótimo tanto quanto se queira, em tempo polinomial para qualquer precisão fixa.

Esses casos especiais explicam por que o TSP, apesar de NP-difícil em geral, é resolvido rotineiramente na prática: a maioria das aplicações reais cai em um desses casos mais tratáveis.

Aplicações reais:

• Logística e roteamento de entregas
• Design de circuitos impressos (minimizar o caminho da sonda de soldagem)
• Sequenciamento de operações em máquinas industriais
• Planejamento de rotas de robôs em armazéns automatizados
• Sequenciamento de DNA em bioinformática
• Posicionamento de telescópios em levantamentos astronômicos

Para o tratamento matemático completo — incluindo variantes assimétricas, formulações de programação linear inteira e os recordes computacionais mais recentes — vale a pena consultar o artigo da Wikipédia sobre o TSP.

Resumo

#

Comparação: Euleriano vs. Hamiltoniano

#

Exercícios

#

Próximos passos

#

Tudo neste artigo tratou de percursos: que sequências de arestas ou vértices um grafo permite percorrer. Em nenhum momento perguntamos como esse grafo pode ser desenhado — se dá para colocá-lo no papel sem que as arestas se cruzem. É exatamente essa a limitação que fecha esta etapa da série: saber que um grafo é euleriano ou hamiltoniano nada diz sobre sua geometria. No próximo artigo, investigamos grafos planares — quando é possível desenhar um grafo no plano sem cruzamento de arestas, e o que isso tem a ver com o famoso Teorema das Quatro Cores que vimos lá no início da série.