Caminho euleriano: diferenças entre revisões
Linha 9: | Linha 9: | ||
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''. |
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. |
Não confundir com [[caminho hamiltoniano]] em que o caminho deve passar uma vez em cada vértice. sim e na se deve confundir nada. |
||
== Ver também == |
== Ver também == |
Revisão das 20h10min de 26 de setembro de 2013
Um Caminho Euleriano é um caminho em um grafo que visita cada aresta apenas 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.
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. Esta condição é também suficiente. 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.[1]
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 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. sim e na se deve confundir nada.
Ver também
Referências
- ↑ BIGGS, N. L.; LLOYD, E. K.; WILSON, R. J. (1976). Graph Theory 1736-1936. Oxford: Clarendon Press. ISBN 0-19-853901-0 Texto "página-8-9" ignorado (ajuda)