Algoritmo de Fleury
Esta página ou se(c)ção precisa ser formatada para o padrão wiki. (Agosto de 2010) |
O algoritmo de Fleury é utilizado para a construção ou identificação de um ciclo euleriano em um grafo euleriano. Um caminho ou um circuito é dito euleriano se ele contém todas as arestas de um grafo. Um grafo que contém um circuito euleriano é um grafo euleriano. Um grafo que não contém um circuito euleriano mas contém um caminho euleriano será chamado grafo semi-euleriano.
A dificuldade em verificar se uma rede é Euleriana reside no grande número de sub-redes possíveis. Este algoritmo pode ser utilizado para resolver problemas como o problema das Pontes de Kaliningrado de uma forma muito mais eficiente.
Lema editar
Para entender como funciona o algoritmo de Fleury, considere o grafo da figura 4a da ligaçao. Suponhamos que o algoritmo começa com o vértice 6. Ele pode escolher uma das arestas h, d, e ou i. Supondo que ele escolhe d, ele se encontra depois no vértice 2, onde ele é obrigado a seguir pela ponte que liga com o vértice 5. Isso é ilustrado na figura 4b. Nesse momento, ele pode escolher entre b, g o h. O último é descartado por ser uma ponte. Então sobram somente b e g. Supondo que b é selecionado, ele chega ao vértice 1, como ilustrado na figura 4c. Nas três próximas etapas, ele não tem escolha. Chegando ao vértice 6, de novo ele tem mais du uma opção. Em mais três etapas, ele volta à origem, o que completa o circuito euleriano.
Pseudocódigo editar
função Fleury(G = (V,E): grafo) : caminho
G' := G { G' = (V', E')}
v0 := um vértice de G'
C := [v0] {Inicialmente, o circuito contém só v0}
Enquanto E' não vazio
vi := último vértice de C
Se vi tem só uma aresta incidente;
ai := a aresta incidente a vi em G'
Senão
ai := uma aresta incidente a vi em G' e que não é uma ponte
Retirar a aresta ai do grafo G'
Acrescentar ai no final de C
vj := vértice ligado a vi por ai
Acrescentar vj no final de C
Retornar C