如何從完整的有向圖構造Hamilton路徑

Question

給定有向圖。

任何2個頂點都相鄰。連接一對頂點的邊可以是單向的或雙向的。

如何找到漢密爾頓路徑？

旁註：

• 維基說「有n個頂點的強連接的簡單有向圖是哈密頓如果每個頂點有一個完整的程度大於或等於n。」因此，我的問題必須存在解決方案。
• 我知道一般的Hamilton路徑問題是NP-Complete。但感覺像這個特定的版本應該有一個多項式解決方案。

Answer 1

使用插入排序的變體來構造二次時間的路徑。鑑於頂點的一個子集的路徑

v1 v2 ... vn-1 

，考慮如何插入vn。如果vn具有到v1的弧段，則前置vn。如果vn-1的弧線爲vn，則附加vn。否則，存在Sperner's lemma索引i，使得vn具有從vi的弧和到vi+1的弧。將它插入那裏。