Menu
Can some one tell me the difference between hamiltonian path and euler path. They seem similar!
808
A cycle that travels exactly once over each edge in a graph is called “Eulerian.” A cycle that travels exactly once over each vertex in a graph is called “Hamiltonian.”
Certain graph problems deal with finding a path between two vertices such that each edge is traversed exactly once, or finding a path between two vertices while visiting each vertex exactly once. These paths are better known as Euler path and Hamiltonian path respectively.
An Euler path is a path that uses every edge of a graph exactly once. An Euler circuit is a circuit that uses every edge of a graph exactly once. ▶ An Euler path starts and ends at different vertices. ▶ An Euler circuit starts and ends at the same vertex.
A path is Eulerian if every edge is traversed exactly once. Clearly, these conditions are not mutually exclusive for all graphs: if a simple connected graph G itself consists of a path (so exactly two vertices have degree 1 and all other vertices have degree 2), then that path is both Hamiltonian and Eulerian.
An Euler path is a path that passes through every edge exactly once. If it ends at the initial vertex then it is an Euler cycle.
A Hamiltonian path is a path that passes through every vertex exactly once (NOT every edge). If it ends at the initial vertex then it is a Hamiltonian cycle.
In an Euler path you might pass through a vertex more than once.
In a Hamiltonian path you may not pass through all edges.
112
(In descending order of generality)
Walk: a sequence of edges where the end of one edge marks the beginning of the next edge
Trail: a walk which does not repeat any edges. All trails are walks.
Path: a walk where each vertex is traversed at most once. (paths used to refer to open walks, the definition has changed now) The property of traversing vertices at most once means that edges are also crossed at most once, hence all paths are trails.
Hamiltonian path: visits every vertex in the graph (exactly once, because it is a path)
Eulerian trail: visits every edge in the graph exactly once (because it is a trail, vertices may well be crossed more than once.)
25
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
