Caminho euleriano

Um Caminho Euleriano é um caminho em um grafo que visita toda aresta exatamente uma vez. Com caso especial, um Circuito Euleriano é um caminho Euleriano que começa e termina no mesmo vértice. O conceito foi introduzido por Leonard Euler para a resolução do famoso problema das sete pontes de Königsberg em 1736.

O grafo das pontes de Königsberg. Este grafo não é Euleriano, portanto, uma solução não existe.

Cada vértice deste grafo tem um grau par,portanto este é um grafo Euleriano. Seguindo as arestas em ordem alfabética obtém-se um circuito/ciclo Euleriano.

Grafos que possuem um circuito Euleriano são chamados Grafos Eulerianos. Uma das principais condições para um grafo ser Euleriano é que todos os vértices precisam ser de grau par. Entretanto, essa condição não é suficiente, pois também é necessário que o grafo seja conexo. Euler provou que uma condição necessária para a existência de circuitos eulerianos é de que todos os vértices tenham grau par, e afirmou, sem prova de que grafos conexos com todos os vértices pares tem um circuito Euleriano. A primeira prova completa desta última afirmação foi publicada em 1873 por Carl Hierholzer.

Há, ainda, grafos com caminhos Eulerianos se houver 2 vértices de grau ímpar. Nesse caso, ao se acrescentar uma aresta ligando estes dois vértices, o novo grafo passa a ser um circuito Euleriano.

Pode-se assim enunciar um corolário do Teorema de Euler para Grafos* como sendo: Um grafo G conexo possui caminho euleriano se e somente se ele tem exatamente zero ou dois vértices de grau impar.

Não confundir com caminho hamiltoniano em que o caminho deve passar uma vez em cada vértice.

Ver também

• Algoritmo de Fleury
• Problema do carteiro chinês
• Caminho hamiltoniano