Como resolver o problema do caminho euleriano na prática
O caminho euleriano é um conceito simples que todo estudante de teoria dos grafos encontra pela primeira vez num curso introdutório. A definição é básica: um caminho que percorre cada aresta de um grafo exatamente uma vez. O que não é tão óbvio é como aplicar isso quando você realmente precisa resolver um problema real, tipo roteirizar um serviço de coleta de lixo ou planejar uma inspeção de redes urbanas.
O que é caminho euleriano e quando ele aparece
Um grafo possui um caminho euleriano se e somente se tem zero ou dois vértices de grau ímpar. Se tiver zero, o caminho começa e termina no mesmo vértice — isso é um circuito euleriano. Se tiver dois, o caminho começa num vértice de grau ímpar e termina no outro. Essa é a condição necessária e suficiente, provada por Euler em 1736 ao resolver o problema das pontes de Königsberg. Agora, o detalhe que poucas pessoas entendem de cara: ter um caminho euleriano não significa que ele é fácil de encontrar manualmente. Em grafos pequenos funciona. Em grafos com milhares de arestas, você precisa de um algoritmo.
Algoritmo de Hierholzer para encontrar o caminho
O algoritmo mais usado na prática é o de Hierholzer, publicado em 1873. Ele funciona assim: você começa de qualquer vértice, segue arestas até ficar sem opções. Quando um ciclo se forma, você "grava" esse ciclo e depois volta a vértices onde ainda há arestas não visitadas, incorporando novos ciclos ao caminho principal. O resultado é um caminho que cobre todas as arestas. A complexidade é O(E), onde E é o número de arestas. Isso é linear e muito eficiente na prática. O código em Python para um grafo representado por lista de adjacência leva cerca de cinquenta linhas, funcionando para grafos direcionados e não-direcionados com pequenas adaptações.
Um insight que aprendi na marra: o algoritmo não carece de uma verificação de conectividade prévia. Se o grafo tiver arestas isoladas em componentes desconexos, Hierholzer vai produzir um caminho válido apenas para o componente do vértice inicial. Sempre verifique se todas as arestas pertencem ao mesmo componente conexo antes de rodar o algoritmo.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Problema real que encontrei com caminho euleriano
Trabalhando num projeto de logística urbana, precisei roteirizar uma van que deveria passar por todas as ruas de um bairro estreito. O grafo tinha cerca de 3.200 vértices e 4.800 arestas, representando ruas em mão dupla e em mão única. Apliquei Hierholzer diretamente e o resultado estava errado: o caminho gerado ignorava algumas ruas laterais. O problema era que o grafo original continha auto-laços e múltiplas arestas entre os mesmos vértices — duas ruas paralelas conectando os mesmos cruzamentos. O algoritmo tratou tudo corretamente em termos matemáticos, mas na vida real, duas arestas entre vértices A e B significavam ruas fisicamente distintas que o motorista precisava percorrer. A solução foi converter o grafo multigrafo para um grafo simples com pesos, duplicando as arestas múltiplas com identificadores únicos para rastreamento, e aí sim aplicar Hierholzer. Isso corrigiu o roteiro em cerca de dez minutos de processamento.
Caminho euleriano versus circuito euleriano: a diferença importa
Muitos confundem os dois conceitos. Um circuito euleriano é um caso especial onde o caminho forma um loop — começa e termina no mesmo vértice. Isso ocorre quando todos os vértices têm grau par. Um caminho euleriano comum permite dois vértices de grau ímpar, funcionando como um trajeto aberto. Na prática logística, isso faz diferença enorme: se seu ponto de partida e chegada é o mesmo (como uma central de distribuição), você precisa de um circuito. Se pode terminar em outro local, um caminho simples basta.
Limitações e quando o caminho euleriano não resolve seu problema
O caminho euleriano clássico tem uma restrição importante: ele exige que TODAS as arestas sejam percorridas. Na maioria dos problemas reais, isso é impossível ou excessivamente custoso. Ruas sem saída, grafos desconectados, restrições de horário — nada disso entra na fórmula básica. Se o grafo não tem caminho euleriano natural, a abordagem comum é o Problema do Carteiro Chinês (Chinese Postman Problem), proposto por Mei-Ko Kuan em 1962. Nele, você duplica arestas existentes para tornar todos os graus pares, minimizando o custo adicional. Para caminhos abertos, existe a variação do Rota de Chinese Postman com extremidades fixas.
Outro cenário onde o caminho euleriano falha completamente: grafos dinâmicos, onde arestas aparecem e desaparecem ao longo do tempo. Sistemas de transporte em tempo real, redes de comunicação com falhas intermitentes — nesses casos, uma abordagem heurística como greedy com re-planejamento periódico funciona melhor do que tentar encontrar um caminho euleriano perfeito.
Implementação prática
Para quem quer testar, a biblioteca NetworkX do Python oferece funções prontas: nx.eulerian_path() para caminhos e nx.eulerian_circuit() para circuitos. O código básico leva menos de trinta linhas e funciona para grafos pequenos e médios (até algumas dezenas de milhares de arestas). Para escalas maiores, considere implementações em C++ ou Rust, que reduzem o tempo de execução de segundos para milissegundos em grafos do mesmo porte. O site GraphOnline.ru permite visualizar caminhos eulerianos em grafos definidos pelo usuário, útil para fins didáticos. Já para uso profissional, ferramentas como o OR-Tools do Google oferecem solvers de roteirização que generalizam o problema euleriano com restrições adicionais de capacidade, janelas de tempo e múltiplos veículos.
