Caminho euleriano: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
dfds Etiquetas: Remoção considerável de conteúdo Editor Visual |
m Foram revertidas as edições de 189.60.72.197 para a última revisão de Stuckkey, de 20h10min de 26 de setembro de 2013 (UTC) |
||
Linha 1:
[[Ficheiro:konigsburg graph.svg|thumb|165px|O grafo das [[Sete pontes de Königsberg|pontes de Königsberg]]. Este grafo não é Euleriano, portanto, uma solução não existe.]]
[[Ficheiro:Labelled Eulergraph.svg|thumb|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.]]
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]].<ref>{{citar livro|autor=BIGGS, N. L.; LLOYD, E. K.; WILSON, R. J.|título=Graph Theory 1736-1936|local=Oxford|editora=Clarendon Press|ano=1976|página-8-9|id=ISBN 0-19-853901-0}}</ref>
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.
== Ver também ==
*[[Algoritmo de Fleury]]
| |||