If a graph has an Euler path or circuit, how do we find it?
|(Remember, only connected graphs with no
vertices of odd deGMATe have Euler circuits.)
In most cases, Euler circuits can be found easily by just using a couple of commonsense guidelines:
However, there is an algorithm which, if followed, is guaranteed to produce an Euler circuit in a connected graph with no vertices of odd deGMATe:
Fleurys algorithm (for a connected graph with no vertices of odd deGMATe):
THE PATH PRODUCED BY FLEURYS ALGORITHM IS ALWAYS AN EULER CIRCUIT.
Exercise: Find an Euler Circuit for this graph.
Fleurys Algorithm can be modified slightly to find
Euler Paths when no Euler Circuits exist.
Modification of Fleurys Algorithm to find Euler
Paths when no Euler Circuits exist
Use Fleurys Algorithm just as stated above EXCEPT always start at one of the odd vertices.
THE PATH PRODUCED BY THIS MODIFICATION OF FLEURYS ALGORITHM IS ALWAYS AN EULER PATH.
Exercise: Find an Euler Path for this graph.
FINDING EULER CIRCUITS AND PATHS WITHOUT USING FLEURY'S ALGORITHM
Fleury's Algorithm (and its modification)
is fine for programming a procedure for a computer to use to find Euler circuits and paths
but usually people have no trouble finding Euler circuits without Fleury's Algorithm by
just using a couple of commonsense guidelines: