Algoritmo de Fleury
# 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.