5.6 Fleury's Algorithm or ...
How
to build a circuit without wires
Topics
Introduction
Fleury's Algorithm
Introduction

Euler's Theorems are examples of existence theorems

existence theorems tell whether or not something exists (e.g. Euler
circuit)

but doesn't tell us how to create it!

we want a constructive method for finding Euler paths and circuits

methods (welldefined procedures, recipes) for construction are called
algorithms

there is an algorithm for constructing an Euler circuit: Fleury's
algorithm

we will illustrate it with the graph:
Fleury's
Algorithm
1. pick any vertex to start
2. from that vertex pick an edge to traverse (see below for important
rule)
3. darken that edge, as a reminder that you can't traverse it
again
4. travel that edge, coming to the next vertex
5. repeat 24 until all edges have been traversed, and you are
back at the starting vertex
at each stage of the algorithm:

the original graph minus the darkened (already used) edges = reduced
graph

important rule: never cross a bridge of the reduced graph
unless
there is no other choice

why must we observe that rule?
Notes:

the same algorithm works for Euler paths

before starting, use Euler’s theorems to check that the graph has an Euler
path and/or circuit to find!

when you do this on paper, you can erase each edge as you traverse it

this will make the reduced graph visible, and its bridges apparent
Example
Step in recipe 
Marked graph 
Reduced graph 
Pick any vertex (e.g. F) 


Travel from F to C
(arbitrary choice) 


Travel from C to D
(arbitrary) 


Travel from D to A
(arbitrary) 


Travel from A to C
(can't go to B: that edge is a bridge of the reduced graph,
and there are two other choices, we chose one of them) 


The rest of the trip is obvious, and the complete Euler circuit is:
(F, C, D, A, C, E, A, B, D, F)