|
|
|
|
Fleury's algorithm
|
(Algorithm)
|
|
|
Fleury's algorithm constructs an Euler circuit in a graph (if it's possible).
- Pick any vertex to start
- From that vertex pick an edge to traverse, considering following rule: never cross a bridge of the reduced graph unless there is no other choice
- Darken that edge, as a reminder that you can't traverse it again
- Travel that edge, coming to the next vertex
- Repeat 2-4 until all edges have been traversed, and you are back at the starting vertex
By “reduced graph” we mean the original graph minus the darkened (already used) edges.
|
"Fleury's algorithm" is owned by mathcam. [ full author list (2) | owner history (1) ]
|
|
(view preamble)
Cross-references: mean, reduced, bridge, edge, vertex, graph, Euler circuit
There is 1 reference to this entry.
This is version 6 of Fleury's algorithm, born on 2003-04-24, modified 2005-04-14.
Object id is 4210, canonical name is FleurysAlgorithm.
Accessed 13708 times total.
Classification:
| AMS MSC: | 05C45 (Combinatorics :: Graph theory :: Eulerian and Hamiltonian graphs) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
