mustish1
asked on
Hamilton Paths and Circuits
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.
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
TommySzalapski
In both cases (Euler and Hamiltonian) the path hits each thing only once (edge or vertex).
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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
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
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
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
>> 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.
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.
Well, yes the travelling salesman problem specifically looks for the shortest Hamiltonian path, but all of them are NP-Complete.
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.
Determining whether a Hamiltonian path exists in a graph is NP-complete,
but a given path is not NP-complete.
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.
The problem of finding either in an arbitrary graph is NP-Complete.