Fleury’s algorithm

Definition

Fleury's algorithm is a method to find an Eulerian path or circuit in a graph. It systematically traverses edges while avoiding breaking the graph into disconnected components until necessary.

5 Must Know Facts For Your Next Test

1. Fleury's algorithm requires the graph to have exactly zero or two vertices of odd degree for an Eulerian path, and no vertices of odd degree for an Eulerian circuit.
2. The algorithm begins at any vertex if finding an Eulerian circuit, or at one of the two odd-degree vertices if finding an Eulerian path.
3. Edges are chosen such that removing them does not disconnect the remaining part of the graph unless it's unavoidable.
4. It uses a process of marking edges as 'used' to ensure each edge is traversed exactly once.
5. Fleury's algorithm has a time complexity of O(E^2) where E is the number of edges in the graph.

Review Questions

• What conditions must a graph satisfy for Fleury's algorithm to find an Eulerian path?
• How does Fleury's algorithm decide which edge to traverse next?
• What is the time complexity of Fleury's algorithm?

Related terms

EulerianPath: A trail in a graph that visits every edge exactly once.

EulerianCircuit: A circuit in a graph that visits every edge exactly once and returns to the starting vertex.

GraphConnectivity: A property that determines whether there exists a path between any two vertices in a graph.