有人可以告诉我汉密尔顿路径和欧拉路径之间的区别。它们看起来很相似！
问问题
111905 次
9 回答
130
欧拉路径是通过每条边恰好一次的路径。如果它在初始顶点处结束，则它是一个欧拉循环。
哈密顿路径是只通过每个顶点一次（不是每条边）的路径。如果它在初始顶点处结束，则它是哈密顿循环。
在欧拉路径中，您可能会多次通过一个顶点。
在哈密顿路径中，您可能不会通过所有边。
于 2010-07-16T21:37:53.450 回答
13
图论定义
（按一般性降序排列）
Walk：一系列边，其中一条边的结束标志着下一条边的开始
Trail：不重复任何边缘的步行。所有的小径都是步行道。
路径：每个顶点最多遍历一次的路径。（路径过去是指开放游走，现在定义已更改） 最多遍历顶点一次的属性意味着边也最多交叉一次，因此所有路径都是路径。
哈密顿路径和欧拉路径
哈密顿路径：访问图中的每个顶点（恰好一次，因为它是一条路径）
欧拉轨迹：只访问图中的每条边一次（因为它是一条轨迹，顶点可能会多次交叉。）
于 2013-01-21T15:50:48.033 回答
9
欧拉路径必须只访问每个边一次，而哈密顿路径必须只访问每个顶点一次。
于 2010-07-16T21:37:08.327 回答
4
它们是相关的，但既不依赖也不相互排斥。如果一个图有一个欧勒环，它可能也有也可能没有哈密顿环，反之亦然。
欧拉循环恰好访问图中的每条边一次。如果图中的顶点有两条以上的边，那么根据定义，循环将多次通过这些顶点。因此，顶点可以重复，但边不能。
哈密顿循环只访问图中的每个顶点一次（类似于旅行商问题）。结果，边和顶点都不能重复。
于 2010-07-16T21:46:03.943 回答
4
我将使用生物学中的一个常见例子；通过制作 DNA 样本来重建基因组。
从头组装
要从短读长构建基因组，有必要构建这些读长的图。我们通过将读取分解为 k-mer 并将它们组装成一个图来做到这一点。
我们可以通过访问每个节点一次来重建基因组，如图所示。这被称为哈密顿路径。
不幸的是，构建这样的路径是 NP 难的。不可能推导出一个有效的算法来解决它。相反，在生物信息学中，我们构建了一个欧拉循环，其中一条边代表一个重叠。
于 2015-11-11T00:26:42.867 回答
3
哈密顿路径恰好访问每个节点（或顶点）一次，而欧拉路径恰好遍历每条边一次。
于 2010-07-16T21:37:26.970 回答
3
欧拉路径 - 欧拉路径是每条边只经过一次的路径。
哈密顿路径 - 哈密顿路径是每个顶点恰好经过一次的路径。
如果您曾经困惑过，请记住 E - Euler E - Edge。
于 2020-04-12T06:40:19.110 回答
1
欧拉路径是只使用图的每条边一次的路径。它必须恰好有两个奇数顶点。路径在不同的顶点开始和结束。哈密顿循环是包含图的每个顶点的循环，因此您可能不会使用图的所有边。
于 2017-04-22T08:50:31.113 回答
0
欧拉路径是使用图的每条边（注意）恰好一次的图。欧拉回路是一条覆盖所有边后返回起点的欧拉路径。
而汉密尔顿路径是一个只覆盖所有顶点（注意）一次的图。当这条路径返回到它的起点时，这条路径被称为汉密尔顿回路。
于 2012-10-08T18:06:12.473 回答