graph-theory - 为什么欧拉路径可以在线性时间内实现，而不是哈密顿路径？

Question

我了解到，即使看似相似，欧拉路径也可以在线性时间内解决，而哈密顿路径问题是 NP 完全的。我想知道造成这种差异的原因是什么？我不太了解图论，所以可能不会很好地理解严格的证明，但一些行话应该没问题。

Answer 1

基本上，欧拉问题可以用动态规划解决，而哈密顿问题则不能。

这意味着，如果您有图形的一个子集并通过它找到有效的圆形路径，您可以将此部分解决方案与其他部分解决方案结合起来，并找到一个全局有效的路径。最优路径并非如此:即使您通过图的一小部分找到了最优路径，这也很可能不是全局最优路径的一部分(事实上，通常不是) .非正式地，通过大图的最佳路径取决于图所有其他部分的确切值，因此没有人找到正确使用“分而治之”的方法来解决问题。