ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 25 Apr 2015 15:32:38 -0500Hierholzer's algorithmhttps://ask.sagemath.org/question/26643/hierholzers-algorithm/ 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.Sat, 25 Apr 2015 13:05:58 -0500https://ask.sagemath.org/question/26643/hierholzers-algorithm/Answer by Nathann for <p>Hi, I have a question, I need to implement Hierholzer's algorithm but I don't know how to start it.
The conditions are:</p>
<p>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.</p>
https://ask.sagemath.org/question/26643/hierholzers-algorithm/?answer=26644#post-id-26644Hello,
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/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.eulerian_circuit
Nathann Sat, 25 Apr 2015 15:32:38 -0500https://ask.sagemath.org/question/26643/hierholzers-algorithm/?answer=26644#post-id-26644