Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I can't come up with an eficcient way to, given a graph, find a path that crosses all edges, only once per each edge, and end in the same vertex that it started.

Can anyone point me in the right direction? I've been looking to do it using strongly-connected components (SCC), but even in a SCC, I can't guarantee, that I can cross all edges, and only once per each one. I can't remember, but I think there is a "standard" algorithm, that finds a path that crosses all edges once.

share|improve this question
1  
What you seek is called an Eulerian cycle, and the concept was popularized by the seven bridges of Königsberg problem. –  Henning Makholm Feb 26 '12 at 21:51
    
Sounds like this: Eulerian path –  draks ... Feb 26 '12 at 21:52
    
@HenningMakholm: If you have an answer, please answer, rather than commenting. For some reasons why: meta.math.stackexchange.com/questions/1559/…. Note: this is just a request! –  Aryabhata Feb 26 '12 at 21:53
    
@Aryabhata: Sure, just went to check whether there was a preëxisting duplicate before starting to type a long answer. But your links will do just as well, I think. –  Henning Makholm Feb 26 '12 at 21:59
add comment

1 Answer

Seems like you are looking for an Euler Circuit, which has standard algorithms. For instance, see Hierholzer's algorithm.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.