Sign in to follow this  
MePHyst0

Euler trail,path...

Recommended Posts

Hello all, I would like to ask whether anybody here knows about an algorhitm which can find the Euler path in a DAC(directed acyclic graph)? I have searched the but didn't seem to find anything useful. I wasn't even able to find and algorhitm to find the Euler path in a simple graph though :) Do anyone know about one? Thanks everybody in advance

Share this post


Link to post
Share on other sites
First note that an Eulerian circuit exists only if the graph has no vertices of even odd degree, and an Eulerian path if there are exactly two (or zero) such.

Provided this condition holds, check out Fleury's algorithm , if you're not too concerned about performance. Also be aware that there are modifications you can make that speed things up.

This problem is paradigmed by the Königsberg Bridges problem and is generalised by the Travelling Salesman problem, if you're looking for more material to Google. Christofides's algorithm is the best solution to the latter problem in existence and may well be what you're looking for.

Regards
Admiral

Edit: Thanks, Zahlman.

[Edited by - TheAdmiral on November 7, 2006 10:38:15 AM]

Share this post


Link to post
Share on other sites
TheAdmiral, =~ s/even/odd, I think.

In a *directed, acyclic* graph, the only way you could have an Euler path would be if there were no branches, in which case the unique path is from root to leaf (where both those nodes have degree 1). This is an obvious result - suppose a node had more than one child: a path would have to visit all children by definition, but one of them would have to come first, and without cycles or reversibility of the 'links', there is no way to get from a (i.e. the first visited) child to any sibling.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this