Algoritmo de Fleury

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

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

   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

Ligações externas

• Grafos eulerianos e hamiltonianos