Caminhos eulerianos

algoritmos, otimizacao basico matematica-discreta, teoria-dos-grafos

Caminhos Eulerianos

Um caminho euleriano é um percurso que usa cada aresta do grafo exatamente uma vez. Se o percurso também termina onde começou, é um circuito euleriano.

Correção

Esta página misturava as duas condições — a de caminho e a de circuito — como se fossem a mesma, e o exemplo usava $K_4$, cujos vértices têm grau ímpar: $K_4$ não tem circuito euleriano nenhum, o oposto do que a página afirmava mostrar.

Teorema de Euler

Para um grafo conexo:

  • Tem circuito euleriano se e somente se todos os vértices têm grau par.
  • Tem caminho euleriano (não necessariamente fechado) se e somente se tem exatamente zero ou dois vértices de grau ímpar. Com dois vértices ímpares, todo caminho euleriano começa num deles e termina no outro.
  • Com mais de dois vértices de grau ímpar, não existe caminho euleriano algum.

$$G \text{ tem circuito euleriano} \iff \forall v \in V: \deg(v) \text{ é par}$$

Exemplo: um grafo euleriano

$K_5$, o grafo completo com 5 vértices, tem todo vértice com grau 4 (par) — logo tem circuito euleriano.

graph TD A((1)) --- B((2)) A --- C((3)) A --- D((4)) A --- E((5)) B --- C B --- D B --- E C --- D C --- E D --- E

Contraexemplo: um grafo não euleriano

$K_4$, o grafo completo com 4 vértices, tem todo vértice com grau 3 (ímpar) — nenhum vértice tem grau par, então não tem circuito euleriano, e como há mais de dois vértices ímpares, também não tem caminho euleriano.

graph TD A((1)) --- B((2)) A --- C((3)) A --- D((4)) B --- C B --- D C --- D

Algoritmo de Hierholzer

O algoritmo de Hierholzer encontra um circuito euleriano em tempo $O(|E|)$:

  1. Escolher qualquer vértice como início
  2. Seguir arestas não visitadas até retornar ao vértice inicial
  3. Enquanto houver arestas não visitadas, encontrar um vértice no circuito atual com arestas não visitadas e repetir

Aplicações

  • Problema do carteiro chinês — encontrar o percurso mais curto que passa por toda aresta ao menos uma vez, mesmo em grafos sem circuito euleriano
  • Roteamento de veículos
  • Projeto de circuitos

Referências

Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein (2009). Introduction to Algorithms. MIT Press. ISBN 9780262533058.
  1. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms. MIT Press. ISBN 978-0-262-53305-8.