爲什麼歐拉路徑可以在線性時間內實現，而不是哈密爾頓路徑？

Question

我瞭解到，儘管看起來相似，歐拉路徑可以在線性時間內解決，而哈密頓路徑問題是NP完全的。我想知道造成這種差異的原因是什麼？我不太瞭解圖論，所以可能不會很好地理解一個嚴格的證明，但是一些術語應該沒問題。

Answer 1

基本上，歐拉問題可以用動態規劃解決，漢密爾頓問題不能。

這意味着如果您有圖的一個子集並通過它找到有效的循環路徑，則可以將此部分解與其他部分解組合，並找到全局有效路徑。對於最佳路徑來說，情況並非如此：即使在通過圖的一小部分找到了最佳路徑之後，這也可能是全局最優路徑的一部分（事實上，它通常並不是最終路徑的一部分） T）。非正式地，通過大圖的最佳路徑取決於圖中所有其他部分的確切值，因此沒有人找到正確使用「分而治之」的方法。

Answer 2

如果我們考慮無向圖的情況，如果圖連通並且只有兩個奇數度的頂點（開始和結束頂點），則存在歐拉路徑。此路徑只訪問一次邊緣。所以，歐拉路徑的存在依賴於頂點的度數而不是頂點的實際數量。

對於哈密爾頓路徑，沒有簡單的必要條件是已知的（當然也沒有多項式時間算法）。由於路徑必須一次打到每個頂點，所以「硬」的方法是檢查頂點的所有排列並查看路徑是否存在。

Answer 3

其實， 哈密頓路徑的限制是你只能訪問一次邊緣。但是歐拉你可能會訪問相同的頂點，有時也會訪問相反方向的相同邊。然而，在大多數情況下，可以創建一個新的頂點，但只可能添加一個邊。

Bellman，R.（1962），「旅行商問題的動態規劃處理」，Journal of the ACM 9：61-63，doi：10.1145/321105.321111。

如果你只是檢查的文章，有一個動態編程實現圖形（不適用於各種課程的圖表）。而也有一些HMM實現爲好，

比約克倫，安德烈亞斯（2010 ），「無向哈密爾頓性的行列式總和」，Proc。第51屆IEEE計算機科學基礎研討會（FOCS'10），第173-182頁，arXiv：1008.0541，doi：10.1109/FOCS.2010.24。

eulerian路徑的好處是;你可以得到子圖（分支和邊界相似），然後得到總週期圖。真相可以說，eulerian大多是爲本地解決方案..

希望有所幫助..