Ask Your Question
0

Hierholzer's algorithm

asked 2015-04-25 13:05:58 -0500

this post is marked as community wiki

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.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2015-04-25 15:32:38 -0500

Nathann gravatar image

Hello,

Your explanation is far from clear, but it seems that Hierholzer's algorithm is meant to give you a eulerian circuit in a eulerian graph. Isn't your problem solved by calling Graph.eulerian_circuit ?

http://www.sagemath.org/doc/reference...

Nathann

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2015-04-25 13:05:58 -0500

Seen: 518 times

Last updated: Apr 25 '15