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

Question

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

Answer 1

欧拉路径是一条路径，它恰好一次穿过每条边而不重复，如果它在初始顶点结束，则它是一个欧拉循环。

汉密尔顿路径通过每个顶点（注意不是每个边缘），恰好一次，如果它在初始顶点结束，则它是哈密顿循环。

在Euler路径中，您可以多次通过顶点。

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

Answer 2

Graph Theory Definitions

（按一般性的降序排列）

• Walk：一系列边缘，其中一条边的末端标记下一条边的开始
• 小径：不重复任何边缘的步行。所有步道都是散步。
• 路径：每个顶点遍历一次的步行路径。 （用于引用开放行走的路径，现在定义已经改变）仅遍历顶点的属性意味着边缘也只交叉一次，因此所有路径都是路径。

Hamiltonian paths & Eulerian trails

• 哈密​​尔顿路径：访问图中的每个顶点（恰好一次，因为它是一条路径）
• 欧拉轨迹：只访问图中的每个边缘一次（因为它是一条轨迹，顶点可能会被多次交叉。）

Answer 3

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

Answer 4

哈密​​尔顿路径只访问每个节点（或顶点）一次，而欧拉路径只遍历每个边缘一次。

Answer 5

它们是相关的，但既不依赖也不相互排斥。如果图形具有Eurler周期，则它可能也可能不具有哈密顿量的cyle，反之亦然。

---

欧拉循环只访问图中的每个边缘一次。如果图中的顶点有两个以上的边，那么根据定义，循环将不止一次地通过这些顶点。因此，顶点可以重复，但边缘不能重复。

哈密​​尔顿循环访问图中的每个顶点一次（类似于旅行商问题）。结果，边缘和顶点都不能重复。

Answer 6

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

新装配

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

我们可以通过访问每个节点重建基因组，如图所示。这被称为哈密顿路径。

不幸的是，构建这样的路径是NP难的。无法推导出有效的算法来解决它。相反，在生物信息学中，我们构建了一个欧拉循环，其中边缘代表重叠。

Answer 7

Euler路径是一个仅使用图形的每个边缘一次的路径。它必须具有正好两个奇数顶点。路径在不同的顶点开始和结束。哈密​​顿循环是一个包含图的每个顶点的循环，因此您可能无法使用图的所有边。

Answer 8

欧拉路径是使用图形的每个边缘（注释）恰好一次的图形。欧拉电路是一条欧拉路径，在覆盖所有边缘后返回到它的起始点。

汉密尔顿路径是一个覆盖所有顶点（注）的图形。当此路径返回其起始点时，此路径称为hamilton circuit。