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: - Always leave one edge available to get back to the starting vertex as the last step.
- Don't use an edge to go to a vertex unless there is another edge available to leave that vertex (except for the last step).
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:
- Pick any vertex as a starting point.
- Marking your path as you move from vertex to vertex, travel along any edges you wish except, DO NOT travel along an edge that is a bridge for the graph formed by the EDGES THAT HAVE YET TO BE TRAVELED-- unless you have to.
- Continue until you return to your starting point.
THE PATH PRODUCED BY FLEURY’S ALGORITHM IS ALWAYS AN EULER CIRCUIT. Exercise: Find an Euler Circuit for this graph. Fleury’s Algorithm can be modified slightly to find
Euler Paths when no Euler Circuits exist.
Use Fleury’s Algorithm just as stated above EXCEPT always start at one of the odd vertices. THE PATH PRODUCED BY THIS MODIFICATION OF FLEURY’S ALGORITHM IS ALWAYS AN EULER PATH. Exercise: Find an Euler Path for this graph.
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: |