为什么欧拉路径可以在线性时间而不是哈密顿路径中实现？

Question

我了解到，尽管看似相似，但欧拉路径可以在线性时间内求解，而哈密顿路径问题是NP完全的。我想知道造成这种差异的原因是什么？我对图论不了解太多，因此可能无法很好地理解严格的证明，但是一些专业术语应该没问题。

Answer 1

基本上，欧拉问题可以通过动态规划解决，而汉密尔顿问题则不能。

这意味着，如果您有图形的一个子集并找到通过它的有效循环路径，则可以将此局部解决方案与其他局部解决方案结合起来，找到全局有效路径。最佳路径并非如此：即使在通过一小部分图形找到最佳路径之后，它也很可能不是全局最佳路径的一部分（实际上，通常不是） 。非正式地，通过大图的最佳路径取决于图的所有其他部分的精确值，因此，没有人找到正确使用“分而治之”的方法。