asked 2015-04-25 13:05:58 -0500
This post is a wiki. Anyone with karma >750 is welcome to improve it.
Hi, I have a question, I need to implement Hierholzer's algorithm but I don't know how to start it. The conditions are:
We started with a vertex v of the graph and either we build a ride (one way) with new edges (not previously used) until we reach a vertex in which no edges remain unused. That vertex v must necessarily, because this ride to reach any other vertex (for the first time or several times), will have used an odd number of edges that come together in him (and, by hypothesis, each vertex has degree par - called degree of a vertex the number of edges that meet in him--). So we have obtained a closed $ C $ promenade that no repeated edges. But perhaps C does not contain all edges of G. If there are edges go, consider the graph G 'that formed from G by removing the edges Ride C (and possible vertices that have been cut). Note that G 'is still satisfy the parity condition grades. Some of the edges of this new graph must have in common a vertex, say w, with the ride C (because G is connected). Now we take w as a new origin with the previous argument, form a closed C ride 'in G' that no repeated edges, and which is attached to C (at least) by w. Redefining now C "inserting" C "in the first vertex have in common. And we repeat the procedure: either we have included all the edges, or locate an edge with a vertex in common with this new C. The process ends when you have used all the edges.