O（N）中的哈密頓循環

Question

我一直在對codility.com問題進行培訓。 Eta 2011有一個問題，它試圖找到獨特的哈密爾頓路徑的數量。 您可以閱讀全部問題here

綜上所述。我們有一個圖，其中每個內部節點恰好連接到另外3個節點，而外部節點連接到1個內部節點。我們繪製一條穿過所有外層節點的路徑。現在所有節點（內部和外部）都連接到3個節點。這是一個無向圖。

他想解決O（N）中的問題！ 可用的解決方案解決了O（2^N）或更高的問題。也有啓發式解決方案，但顯然它們並不精確。 使用圖中每個節點恰好連接到其他三個節點的知識，是否有可能解決O（N）中的哈密爾頓路徑？

由於版權問題，我相信我無權複製/粘貼整個問題。但第一段提供了一個鏈接。

歡呼 Moataz

Answer 1

從wikipedia：

...他們仍然NP完全即使對於 最大程度的無向平面圖3

所以，除非你有更多的關於圖結構的信息，入度3的所有平面圖都是這個問題的可能輸入情況的一個子集，因此如果你可以解決這個問題pol在一般情況下 - 您也可以針對所有具有度數爲3的多項式的平面圖解決問題，並且可以得出結論：P=NP

Answer 2

Hamiltonian cycle是圖的某些子集的多項式。 co-comparability graphs。

如果您的輸入圖是其中一個這樣的圖，您可以用多項式時間解決問題。請注意，我並不是說哈密頓週期不是NP-C。我只是說它對於某些圖是多項式的。

因此，如果您的輸入圖是共同可比性圖，那麼您有一個多項式解。

Answer 3

該圖基本上是一棵樹，根節點有3個子節點，所有其他非葉節點有2個子節點。葉子從左到右連接。

您可以將每個子樹看作具有兩個端點葉節點（比如開始和結束）。

現在給出了一個以節點n爲根的子樹。如果哈密爾頓路由不涉及n並且它是父節點，那麼它將涉及從開始到結束的路徑並將覆蓋子樹的所有頂點（實際上，在n處路由的子樹中的麻煩路由）。

現在考慮樹的根。假設我們對x和y採取邊緣，x是左邊，y是右邊。

現在我們必須從x的根樹到子樹的終點，y的子樹的起點。

（數字有幫助）。

路徑的其餘部分通過連接自己需要路徑的子樹的開始到結束來完成。

這給出了遞歸算法，並且可以在我相信的O（n）時間內計算出來。

瘋狂的期望30分鐘。

Answer 4

首先，考慮具有根的樹和所有非葉子節點都有兩個孩子。 葉子也從左到右連接，但第一片葉子是不是連接 到最後。有多少路徑從最左邊到最右邊的葉子？

答案是只有一個，這並不難證明。

現在從輸入中取樹。選擇任何節點並刪除它的一個邊。 你剩下兩棵與我在開頭提到的結構相同的樹。 使用這兩個，你可以建立一個哈密爾頓路徑。

現在你選擇的節點有三條邊你可以刪除，因此有三條路到 使哈密爾頓路徑總共:)。

因此，代碼歸結爲檢查一致性和寫3，以防萬一。 30分鐘真的不是那麼瘋狂。