Caminhos eulerianos

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

Caminhos Eulerianos

Um grafo euleriano é um grafo onde é possível percorrer todas as arestas exatamente uma vez.

Definição Formal

Um grafo conectado é euleriano se e somente se todos os seus vértices têm grau par.

$$G = (V, E) \text{ é euleriano } \iff \forall v \in V: \deg(v) \text{ é par}$$

Teorema de Euler

Um grafo conexo tem um circuito euleriano se e somente se todos os seus vértices têm grau par.

Exemplo

Considere o grafo $K_4$ (grafo completo com 4 vértices):

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
[ref]

Aplicações

  • Problema do carteiro chinês[ref]
  • Roteamento de veículos
  • Diseño 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.