Fleury's Algorithm and Euler's Paths and Cycles
On a graph, an Euler's path is a path that passes through all the edges of the graph, each edge exactly once. Euler's path which is a cycle is called Euler's cycle. For an Euler's path to exists, the graph must necessarily be connected, i.e. consists of a single connected component. Connectivity of the graph is a necessary but not a sufficient condition for the existence of an Euler path. For a connected graph, an Euler path exists if and only if the number of odd vertices is either 0 or 2; in the former case any Euler path is a cycle. In the latter case, the path starts at one and terminates at the other of the odd vertices.
Fleury's algorithm is a simple prescription for finding Euler paths and the applet below helps you master Fleury's algorithm. The instructions for using the applet are available on a separate page and can also be read under the first tab directly in the applet.
| What if applet does not run? |
(This applet was created to accompany Excursions in Modern Mathematics, Seventh Edition, by Peter Tannenbaum © Pearson Education. Reproduced with permission.)
Fleury's algorithm works by simply constructing a path, starting at an arbitrary vertex (or at an odd one if there are any) and picking any of its incident edges, with a single caveat: any edge is permissible but those that leave the remaining graph disconnected. (For a connected graph, an edge whose removal affects the connectivity of the graph is called a bridge.)
- Graphs Fundamentals
- Crossing Number of a Graph
- Regular Polyhedra
- 3 Utilities Puzzle: Water, Gas, Electricity
- A Clique of Acquaintances
- Round Robin Tournament
- The Affirmative Action Problem
- The Two Men of Tibet Problem
- Euler Cycles in Digraph
- Fleury's Algorithm and Euler's Paths and Cycles: an Interactive Gizmo
- Graph with Nodes of Even Degree
- Graph without 3-Cycles
|Activities| |Contact| |Front page| |Contents|
Copyright © 1996-2018 Alexander Bogomolny71862906