5.6 Fleury's Algorithm or ...

How to build a circuit without wires

Fleury's Algorithm



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 2-4 until all edges have been traversed, and you are back at the starting vertex

at each stage of the algorithm:

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 
Travel from D to A 
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)