We help IT Professionals succeed at work.

Hamilton Paths and Circuits

mustish1
mustish1 asked
on
Hi guys: Can any one please tell me the difference between Hamilton Paths and Hamilton Circuits?

I know about Euler's Path and Euler's Circuit

A path in a multigraph G that includes exactly once all the edges of G and has different first and last vertices is called an Euler path.

If this path has the  same initial and terminal vertices, we call it an Euler circuit.

IS THERE ANY THING COMMON BETWEEN EULER AND HAMILTON?  

THANKS.
Comment
Watch Question

Awarded 2010
Top Expert 2013
Commented:
Your question you deleted about Euler paths was wrong. Are you sure you know them well enough?

Anyway, Hamiltonian is paths through all vertices and Euler is paths through all edges.
A circuit is just a path that has the same start and end point whether it's Euler or Hamiltonian.

Euler paths are easy to find. If all vertices have even degree then the circuit (and paths) exist. If two vertices have odd degree and the rest are even, then paths exist but no circuits. (You can't have only one with an odd degree and of course this assumes the graph is connected).

Hamiltonian is significantly harder. They are commonly called the "Travelling salesman" problem and they have been shown to be NP-Complete which basically means that the only way to find out if such a path exists is to check every single possible path (which can take forever). Currently there is no known way to find if Hamiltonian paths exist in a reasonable amount of time.
Awarded 2010
Top Expert 2013

Commented:
In both cases (Euler and Hamiltonian) the path hits each thing only once (edge or vertex).
Please see this link:

http://en.wikipedia.org/wiki/Hamiltonian_path

Basically, a cicly is a path with a final edge tha joins the first vertex with the end vertex, so the path becomes a cycle.

Hope this helps. Regards

Author

Commented:
I correct my Eulers defination above as I watch a video about Eulers path and Eulers circuit in youtube but couldnt find any thing which shows about Hamilton

Commented:
Sounds like this is a schoolwork question.  We're not really supposed to give you the answers for that.

However, I can give you the definition of a Hamiltonian path and circuit.  You can then use that info to see what they do/don't have in common.

A Hamiltonian path (or traceable path) is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex
ozo
Most Valuable Expert 2014
Top Expert 2015
Commented:
A Hamiltonian path visits each vertex exactly once
>> Hamiltonian is significantly harder. They are commonly called the "Travelling salesman" problem and they have been shown to be NP-Complete which basically means that the only way to find out if such a path exists is to check every single possible path (which can take forever). Currently there is no known way to find if Hamiltonian paths exist in a reasonable amount of time.

Isn't that true only if you are trying to find a Hamiltonian path which has a minimum weight? For example, if the vertices represent cities, and the edges represent the travelling cost between the cities, then a salesman may wish to minimize his total travelling cost as he goes from city to city. There may be multiple Hamiltonian paths, but some may have larger travelling costs than others.
Awarded 2010
Top Expert 2013

Commented:
Well, yes the travelling salesman problem specifically looks for the shortest Hamiltonian path, but all of them are NP-Complete.
ozo
Most Valuable Expert 2014
Top Expert 2015

Commented:
When you say "all of them are NP-Complete", what does "them" refer to?  A given instance of the travelling salesman problem is not NP-complete.  The class of travelling salesman problems in general is NP-complete.
Determining whether a Hamiltonian path exists in a graph is NP-complete,
but a given path is not NP-complete.
Awarded 2010
Top Expert 2013

Commented:
By "all of them" I meant the travelling salesman and Hamiltonian path problems.
The problem of finding either in an arbitrary graph is NP-Complete.