# Euler trail,path...

This topic is 4269 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
At first glance, it looks like a simple tree traversing algorithm would solve it sufficiently.

##### 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

Edit: Thanks, Zahlman.

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

##### Share on other sites

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.

1. 1
Rutin
19
2. 2
JoeJ
15
3. 3
4. 4
5. 5

• 24
• 20
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631699
• Total Posts
3001776
×