logo标签列表

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

algorithmgraphgraph-theoryhamiltonian-patheuler-path
69

请问有人能告诉我哈密顿路径和欧拉路径的区别吗？它们看起来很相似！

6
我已删除了C/C++标签。如果您确实正在寻找关于欧拉/哈密顿路径算法的代码，请随意添加它们回来。 - Aryabhatta
1
一条路径恰好包含每个顶点一次（在闭合路径/循环的情况下，第一个/最后一个顶点可能是例外）。因此，术语“欧拉路径”或“欧拉循环”对我来说似乎是具有误导性的。它应该是“欧拉迹”或“欧拉回路”。 - Md. Abu Nafee Ibna Zahid
我同意Md. Abu Nafee的观点。Euler path这个名称似乎有误导性，因为其中顶点是重复的。它的原始名称是Eulerian trail。Euler path是一个错误的叫法。 - srbcheema1
9个回答
134

欧拉路径是指恰好经过每条边一次的路径，若该路径以起始顶点结束，则称为欧拉回路。

哈密顿路径是指恰好经过每个顶点一次（而非每条边）的路径，若该路径以起始顶点结束，则称为哈密顿回路。

在欧拉路径中，可能会多次通过某些顶点。

在哈密顿路径中，可能无法经过所有边。

2
请注意，在欧拉路径中，您可能会多次访问每个顶点，在哈密顿路径中，不必遍历每条边。来自：http://pballew.net/graphs.html - NG.
4
据我所知，判断一个图是否存在欧拉路径（或欧拉回路）很容易，但是判断一个图是否存在哈密顿回路则是NP完全问题。 - David Thornley
是的，我相信存在欧拉路径的某些属性，可以用来证明一个图有欧拉路径，而不需要遍历它的算法。寻找哈密顿路径是NP完全问题，我认为算法涉及试错。我认为将其添加到答案超出了原始问题的范围，OP显然是图论新手:D 我已经很久没有接触这方面的知识了，我可能会翻出我的旧书。 - Chris Diver
2
一条路径恰好经过每个顶点一次（特殊情况下可能是首尾顶点，即闭合路径/环）。因此，“欧拉路径”或“欧拉回路”这一术语似乎对我来说有些误导性。应该使用“欧拉迹”或“欧拉电路”。 - Md. Abu Nafee Ibna Zahid
1
我同意Md. Abu Nafee的观点。Euler path这个名称似乎有误导性，因为其中包含了重复的顶点。它的原始名称应该是Eulerian trail。Euler path是一个错误的叫法。 - srbcheema1
显示剩余2条评论
12

图论定义

(按照概括程度降序)

  • 步行(Walk): 一系列边，其中一个边的末尾标记了下一个边的开始。

  • 迹(Trail): 不重复任何边的步行。所有迹都是步行。

  • 路径(Path): 每个顶点最多遍历一次的步行。 (路径曾用于指代开放步行，现在的定义已经改变) 遍历每个顶点最多一次的属性意味着边也最多被穿越一次，因此所有路径都是迹。

哈密顿路径和欧拉迹

  • 哈密顿路径(Hamiltonian path): 访问 图中的每个顶点 (恰好一次，因为它是一条路径)

  • 欧拉迹(Eulerian trail): 访问 图中的每条边 恰好一次 (因为它是一条迹，顶点可能会被多次穿越。)

2
+1 是考虑“路径”（每个顶点恰好遍历一次）的定义。我认为术语“欧拉路径”或“欧拉回路”有误导性，它应该总是被称为“欧拉迹”或“欧拉电路”。不幸的是，其他答案没有考虑“路径”的定义。 - Md. Abu Nafee Ibna Zahid
1
请在这些定义中添加官方来源链接。 - root-11
9

欧拉路径必须恰好经过每条边一次，而哈密顿路径必须恰好经过每个顶点一次。

一条路径（Path）恰好包含每个顶点一次（在闭合路径/循环的情况下，第一个/最后一个顶点可能是例外）。因此，我认为“欧拉路径”或“欧拉循环”这个术语有些误导。它应该是“欧拉迹”或“欧拉回路”。 - Md. Abu Nafee Ibna Zahid
请在这些定义的官方来源中添加链接。 - root-11
4
他们之间有联系，但并不相互依存或互斥。如果一个图有欧拉回路，则该图也可能有哈密顿回路，反之亦然。
欧拉回路会恰好遍历图中的每一条边。如果图中有具有两个以上边的顶点，则根据定义，该回路将多次穿过这些顶点。结果，可以重复顶点但不能重复边。 哈密顿回路会恰好遍历图中的每一个顶点（类似于旅行商问题）。结果，既不能重复边也不能重复顶点。
1
你将路径和电路混淆了。哈密顿/欧拉电路是一种适当类型的路径/轨迹，它还从同一个节点开始和结束。 - Yaniv
1
一条路径（Path）恰好包含每个顶点一次（在闭合路径/循环的情况下，第一个/最后一个顶点可能是例外）。因此，我认为“欧拉路径”或“欧拉循环”这个术语有些误导。它应该是“欧拉迹”或“欧拉回路”。 - Md. Abu Nafee Ibna Zahid
4
我会尽力帮助您进行翻译。以下是需要翻译的内容：

我将使用生物学中的一个常见示例；通过制作DNA样本来重建基因组。

De-novo组装

为了从短读取中构建基因组，需要构建这些读取的图形。我们通过将读取分解成k-mers并将它们组装成图形来实现。

enter image description here

我们可以通过访问每个节点来重建基因组，就像图表中所示的那样。这被称为哈密顿路径。
不幸的是，构建这样的路径是NP难问题。无法得出有效算法来解决它。在生物信息学中，我们构建一个欧拉循环，其中一条边表示重叠。

enter image description here

3
一个哈密顿路径恰好访问每个节点（或顶点）一次，而欧拉路径则恰好遍历每条边一次。
一条路径（Path）恰好包含每个顶点一次（在闭合路径/循环的情况下，第一个/最后一个顶点可能是例外）。因此，我认为“欧拉路径”或“欧拉循环”这个术语有些误导。它应该是“欧拉迹”或“欧拉回路”。 - Md. Abu Nafee Ibna Zahid
1

欧拉路径 - 欧拉路径是一条每个边恰好经过一次的路径。

哈密顿路径 - 哈密顿路径是一条每个顶点恰好经过一次的路径。

如果您有任何疑问，请记住 E - 欧拉 E - 边。

1
一条欧拉路径是指恰好使用图中每条边一次的路径，并且该路径必须有恰好两个奇数顶点，路径起点和终点不同。哈密顿环是包含图中每个顶点的循环，因此可能不使用图中所有的边。
0

欧拉路径是一种使用图形的每条边（注意）仅一次的图形。欧拉回路是一种欧拉路径，它在覆盖所有边缘后返回其起点。

而哈密顿路径则是一种覆盖所有顶点（注意）仅一次的图形。当此路径返回到其起点时，则称此路径为哈密顿回路。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接