哈密顿路径和欧拉路径之间的区别

Question

有人可以告诉我汉密尔顿路径和欧拉路径之间的区别.他们似乎相似!

Answer 1

的欧拉路径是正好一次越过每边不重复,如果在初始顶点结束则它是欧拉循环的路径.

甲汉弥尔顿路径穿过每个顶点(注意不是每个边缘),正好一次,如果在初始顶点结束则它是哈密顿周期.

在Euler路径中,您可以多次通过顶点.

在哈密尔顿路径中,您可能无法通过所有边缘.

IIRC,很容易找到是否存在欧拉路径(或循环),但是图形是否具有哈密顿量是NP完全的. (3认同)
来自:http://pballew.net/graphs.html请注意,对于欧拉路径,您可以多次访问每个顶点,并且在汉密尔顿路径中,不必每个边缘都行进. (2认同)
路径只包含每个顶点一次（在封闭路径/循环的情况下，第一个/最后一个顶点可能除外）。所以术语 **Euler Path** 或 **Euler Cycle** 对我来说似乎是一种误导。它应该是 **Euler Trail** 或 **Euler Circuit**。 (2认同)

Answer 2

(按一般性的降序排列)

+1 用于考虑 **Path** 的定义（每个顶点恰好遍历一次）。术语 **Euler Path** 或 **Euler Cycle** 对我来说似乎具有误导性。它应该始终是 **Euler Trail** 或 **Euler Circuit**。不幸的是，其他答案没有考虑 **Path** 的定义。 (2认同)

Answer 3

欧拉路径必须完全访问每个边缘一次,而哈密尔顿路径必须访问每个顶点一次.

哈密​​顿路径和欧拉路径之间的区别