1
$\begingroup$

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.

  • 1
    What you seek is called an _Eulerian cycle_, and the concept was popularized by the _seven bridges of Königsberg_ problem.2012-02-26
  • 0
    Sounds like this: [Eulerian path](http://en.wikipedia.org/wiki/Eulerian_path)2012-02-26
  • 0
    @HenningMakholm: If you have an answer, please answer, rather than commenting. For some reasons why: http://meta.math.stackexchange.com/questions/1559/dealing-with-answers-in-comments. Note: this is just a request!2012-02-26
  • 0
    @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.2012-02-26

1 Answers 1