Difference between hamiltonian path and euler path

问题:

Can some one tell me the difference between hamiltonian path and euler path. They seem similar!

回答1:

An 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 through all edges.

回答2:

Graph Theory Definitions

(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 exactly once. (paths used to refer to open walks, the definition has changed now) The property of traversing vertices just once means that edges are also crossed just once, hence all paths are trails.

Hamiltonian paths & Eulerian 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.)

回答3:

Eulerian path must visit each edge exactly once, while Hamiltonian path must visit each vertex exactly once.

回答4:

A Hamiltonian path visits every node (or vertex) exactly once, and a Eulerian path traverses every edge exactly once.

回答5:

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.

回答6:

I'll use a common example in biology; reconstructing a genome by making DNA samples.

De-novo assembly

To construct a genome from short reads, it's necessary to construct a graph of those reads. We do it by breaking the reads into k-mers and assemble them into a graph.

We can reconstruct the genome by visiting each node once as in the diagram. This is known as Hamiltonian path.

Unfortunately, constructing such path is NP-hard. It's not possible to derive an efficient algorithm for solving it. Instead, in bioinformatics we construct a Eulerian cycle where an edge represents an overlap.

回答7:

An Euler path is a path that uses every edge of a graph exactly once.and it must have exactly two odd vertices.the path starts and ends at different vertex. A Hamiltonian cycle is a cycle that contains every vertex of the graph hence you may not use all the edges of the graph.

回答8:

Euler path is a graph using every edge(NOTE) of the graph exactly once. Euler circuit is a euler path that returns to it starting point after covering all edges.

While hamilton path is a graph that covers all vertex(NOTE) exactly once. When this path returns to its starting point than this path is called hamilton circuit.