Can some one tell me the difference between Hamiltonian path and euler path. Both seems similar!
Thanks & Regards,
Mousey
+4
A:
Eulerian path must visit each edge exactly once, while Hamiltonian path must visit each vertex exactly once.
Roman Cheplyaka
2010-07-16 21:37:08
+2
A:
A Hamiltonian path visits every node (or vertex) exactly once, and a Eulerian path traverses every edge exactly once.
burningstar4
2010-07-16 21:37:26
+10
A:
A Euler path is a path that crosses every edge exactly once without repeating, if it ends at the initial vertex then it is a Euler cycle.
A Hamiltonian path passes through each vertex (note not each edge), exactly once, if it ends at the initial vertex then it is a Hamiltonian cycle.
In a Euler path you might pass through a vertex more than once.
In a Hamiltonian path you may not pass though all edges.
Chris Diver
2010-07-16 21:37:53
from: http://pballew.net/graphs.htmlNotice that for an Euler path you may visit each vertex more than once and in a Hamilton path it is not necessary to travel every edge.
SB
2010-07-16 21:41:04
Added to the answer thanks @SB
Chris Diver
2010-07-16 21:44:24
IIRC, it's easy to find if there's a Euler path (or cycle), but whether a graph has a Hamiltonian is NP-complete.
David Thornley
2010-07-16 21:58:27
Yes, I believe there are certain properties of a Euler path which you can use to prove a graph has a Euler path without an algorithm to traverse it. Finding a Hamiltonian path is an NP-complete, i think the algorithm involves trial and error. I thought this would be beyond the scope of the original question to add it to the answer, the OP is obviously new to graph theory :D It's been a while for me, I might dig out my old books.
Chris Diver
2010-07-17 02:48:42
+2
A:
They are related but are neither dependent nor mutually exclusive. If a graph has an Eurler cycle, it may or may not also have a Hamiltonian cyle and vice versa.
Euler cycles visit every edge in the graph exactly once. If there are vertices in the graph with more than two edges, then by definition, the cycle will pass through those vertices more than once. As a result, vertices can be repeated but edges cannot.
Hamiltonian cycles visit every vertex in the graph exactly once (similar to the travelling salesman problem). As a result, neither edges nor vertices can be repeated.
advait
2010-07-16 21:46:03