Difference Between Hamiltonian Path and Eulerian Path
The Hamiltonian and Eulerian paths are two significant concepts used to the solve various problems related to the traversal and connectivity of the graphs. Understanding the differences between these two types of the paths is crucial for the designing efficient algorithms and solving the complex graph problems.
What is a Hamiltonian Path?
Hamiltonian path in the graph is a path that visits the each vertex exactly once. If such a path exists in the graph the graph is said to the have a Hamiltonian path. When the path starts and ends at the same vertex and it is called a Hamiltonian cycle or circuit.
Given a graph G(V, E), where V is the set of vertices and E is the set of edges, a Hamiltonian Path is a sequence of vertices (v1, v2, …,vn) such that each vertex in V appears exactly once in the sequence, and for every i, 1<=i<n, there exists an edge (vi, vi+1) in E.
Example:
What is an Eulerian Path?
Eulerian path in a graph is a path that visits the every edge exactly once. If such a path exists in the graph, the graph is said to the have an Eulerian path. When the path starts and ends at the same vertex and it is called an Eulerian circuit or Eulerian cycle.
Given a graph G(V, E), a Eulerian Path is a sequence of edges (e1, e2,…,en), such that each edge in E appears exactly once in the sequence, and for every i, 1 <= i < n, there exists a vertex v that is incident to both ei and ei+1.
Example:
Hamiltonian Path vs. Eulerian Path:
Below is the table listing the difference between Hamiltonian Path and Eulerian Path:
|
Characteristics |
Hamiltonian Path |
Eulerian Path |
|---|---|---|
|
Definition |
Visits each vertex exactly once |
Visits each edge exactly once |
|
Existence Condition |
NP-complete problem and no simple characterization |
Exists if exactly 0 or 2 vertices have odd degree |
|
Hamiltonian Cycle |
Starts and ends at the same vertex |
Eulerian Circuit: starts and ends at the same vertex |
|
Problem Complexity |
NP-complete |
Polynomial time |
|
Example Graph Types |
TSP (Traveling Salesman Problem) and pathfinding |
Bridges of Königsberg and mail routing |
Both Hamiltonian and Eulerian paths are fundamental concepts in graph theory. Hamiltonian Path focus on visiting vertices, whereas Eulerian Paths focus on traversing edges.