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.

 

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy 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.)

|Activities| |Contact| |Front page| |Contents| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 62015766

Search by google: