漢密爾頓路徑檢查器

檢查圖中是否包含漢密爾頓路徑或漢密爾頓迴圈。執行帶有 Warnsdorff 修剪的回溯演算法，驗證連通性與度數前提條件，測試 Dirac 和 Ore 充分條件，並在動畫 SVG 可視化中顯示見證路徑。

漢密爾頓路徑檢查器

漢密爾頓路徑檢查器 用於判定圖形是否包含 漢密爾頓路徑（訪問每個頂點恰好一次的序列）或 漢密爾頓迴圈（額外回到起始頂點的路徑）。它結合了快速的結構預檢查（連通性、度數先決條件、Dirac 定理、Ore 定理）與 Warnsdorff 啟發式優化的回溯搜尋，並透過逐步動畫視覺化見證路徑。

什麼是漢密爾頓路徑？

給定一個具有 n 個頂點的圖 G = (V, E)，漢密爾頓路徑 是所有頂點的一個有序序列 v₁, v₂, …, v_n，使得每一對連續的頂點 (v_i, v_i+1) 都是 G 的一條邊，且每個頂點恰好出現一次。如果額外滿足 (v_n, v₁) 也是一條邊，則該序列稱為 漢密爾頓迴圈。

漢密爾頓路徑: v1 — v2 — v3 — … — vn (全部不同，每對連續頂點為一邊) 漢密爾頓迴圈: v1 — v2 — v3 — … — vn — v1 (閉合回到起點)

此問題以 William Rowan Hamilton 的名字命名。他在 1857 年發明了 Icosian game（二十面體遊戲），要求解題者在正十二面體的頂點上找到一個恰好訪問每個頂點一次的迴圈。

為何困難：NP-Completeness

漢密爾頓路徑判定問題和漢密爾頓迴圈判定問題都是 NP-complete（Karp, 1972）。除非 P = NP，否則不存在能解決所有情況的多項式時間演算法。在最壞的情況下，回溯搜尋需要探索大小達 (n−1)! 的搜尋樹。這就是為什麼本計算機將輸入限制為 20 個頂點的原因 —— n 的微小增加會導致執行時間呈爆炸式增長。

在實踐中，Warnsdorff 啟發式（由 Heinrich Warnsdorff 於 1823 年針對騎士巡邏問題提出）使結構化圖形的搜尋速度大幅提升：在每一步中，演算法將當前路徑延伸到具有最少剩餘未訪問鄰居的未訪問頂點。這種貪婪規則能防止搜尋陷入死角，並經常在性能良好的圖形上找到無回溯的漢密爾頓巡迴。

必要條件 —— 快速拒絕

在執行昂貴的搜尋之前，本計算機會拒絕那些絕對不可能包含漢密爾頓路徑的圖形：

連通性。 漢密爾頓路徑必須訪問每個頂點，因此圖形必須恰好有一個連通分量。對於有向圖，需要弱連通性（忽略箭頭方向）。
度數 (無向)。 最多只能有兩個頂點的度數為 1 —— 它們是路徑端點的僅有候選者。對於漢密爾頓迴圈，每個頂點的度數必須至少為 2。
度數 (有向)。 對於漢密爾頓路徑，最多只能有一個頂點入度為 0（起點），且最多只有一個頂點出度為 0（終點）。對於漢密爾頓迴圈，每個頂點的入度與出度都必須 ≥ 1。

這些規則能在線性時間內拒絕許多無望的輸入，避免浪費回溯精力。

充分條件 —— 經典定理

幾條經典定理給出了保證無向簡單圖中存在漢密爾頓迴圈的充分（但非必要）條件。如果其中任何一條適用，計算機會將結果標記為「保證存在」而無需運行搜尋 —— 儘管它仍會展示一個見證迴圈。

Dirac 定理 (1952)

如果 G 是一個頂點數 n ≥ 3 的簡單無向圖，且每個頂點的度數至少為 n / 2，則 G 具有漢密爾頓迴圈。

δ(G) ≥ n / 2 ⟹ G 具備漢密爾頓性

Ore 定理 (1960)

如果對於每一對不相鄰的頂點 u 和 v，我們有 deg(u) + deg(v) ≥ n，則 G 具有漢密爾頓迴圈。Ore 的條件嚴格來說比 Dirac 的更弱，因此 Ore 定理蘊含了 Dirac 定理。

∀ 不相鄰頂點 u, v: deg(u) + deg(v) ≥ n ⟹ G 具備漢密爾頓性

未能滿足 Dirac 或 Ore 條件並不代表圖形缺乏漢密爾頓迴圈 —— 許多圖形兩者都不滿足但仍包含一個（例如，一個簡單的 n-迴圈最小度數為 2，在 n 較大時遠低於 n/2）。

內部搜尋演算法

當預檢查無法確定結果時，計算機會在圖形的鄰接表示上執行回溯搜尋。關鍵策略包括：

位元遮罩訪問集。 已訪問的頂點以位元遮罩形式儲存（對於最多 20 個頂點，O(1) 快速成員測試）。
Warnsdorff 啟發式。 在每次延伸時，按鄰居剩餘的未訪問度數排序嘗試（最小優先），模擬「低分叉」順序。
根節點選擇。 對於漢密爾頓迴圈，只需要一個起始頂點（迴圈具有旋轉不變性）。對於漢密爾頓路徑，按出度升序嘗試起點 —— 優先嘗試最稀有的位置。
步驟預算。 設有硬性上限以防止病態實例無限執行；如果預算耗盡，UI 將報告 verdict 為「逾時」。

漢密爾頓 vs 歐拉

漢密爾頓問題與歐拉問題很容易混淆 —— 它們聽起來很像，但本質上完全不同：

屬性	漢密爾頓路徑 / 迴圈	歐拉跡 / 迴圈
訪問每個…	頂點恰好一次	邊恰好一次
複雜度	NP-complete	多項式 (O(n+m))
條件	無簡單特徵描述	連通 + 所有度數為偶數 (迴圈)；最多 2 個奇數度頂點 (跡)
命名自	W. R. Hamilton (1857)	L. Euler (1736, 柯尼斯堡七橋)
經典範例	旅行推銷員問題, Icosian game	路線檢查, 郵差問題

支援的輸入格式

邊列表

每行一條邊，或以逗號分隔。支援的分隔符號：A-B, A B, A,B, A--B, A->B, A<-B。使用 -> 強制解釋為有向邊。

A-B, B-C, C-D, D-A, A-C (5 條邊的無向圖) A->B, B->C, C->D, D->A (有向 4-迴圈)

鄰接矩陣

0/1 值的方陣，每行一列，以空格或逗號分隔。在「矩陣標籤」欄位中提供選填標籤；否則將自動使用 A, B, C…。

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

如何使用此檢查器

挑選輸入格式 —— 手寫小型圖形選「邊列表」，從程式碼或教科書貼上選「鄰接矩陣」。
貼上您的圖形 到文字區域。對於矩陣輸入，可選擇提供頂點標籤。
選擇檢查項目：單次運行檢查路徑、迴圈或兩者。
選擇圖形類型 —— 「自動檢測」會根據箭頭樣式 (->) 或矩陣對稱性推斷有向性。
點擊「檢查漢密爾頓」。 結果頁面會顯示判定標題、必要條件預檢查、Dirac / Ore 充分條件測試、見證路徑（如果存在）以及互動式視覺化。
重播見證，使用「播放 / 單步」控制。觀看路徑在圖上一邊一邊地亮起。

實例演示 —— Petersen 圖

著名的 Petersen 圖（10 個頂點，15 條邊，3-正則圖）是具有漢密爾頓路徑但沒有漢密爾頓迴圈的教科書範例。將此內容貼到邊列表欄位並點擊檢查：

1-2, 2-3, 3-4, 4-5, 5-1, 6-8, 8-10, 10-7, 7-9, 9-6, 1-6, 2-7, 3-8, 4-9, 5-10

檢查器確認：找到漢密爾頓路徑（例如 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3），但窮舉搜尋未發現閉合回到起點的方法 —— 這一結果最早在 1890 年代得到證明。

常見應用

路由與旅行推銷員問題 (TSP) —— 每個 TSP 巡迴都是完全權重圖中的一個漢密爾頓迴圈。
基因組組裝 —— 從重疊讀數重建 DNA 序列可以建模為重疊圖中的漢密爾頓路徑。
電路佈局 —— 在 PCB 上排列引腳以實現最小佈線長度。
遊戲 AI 與謎題求解 —— 棋盤上的騎士巡邏、Icosian game。
排程 —— 安排任務序列，使每個任務都能可行地過渡到下一個。
組合數學教學 —— 透過可手動求解的小型範例說明 NP-completeness。

常見問題

什麼是漢密爾頓路徑？

漢密爾頓路徑是圖中經過每個頂點恰好一次的走法。它以 William Rowan Hamilton 的名字命名，他在 1857 年研究了十二面體圖上的這個問題。判定是否存在這樣的路徑是一個 NP-complete 問題，因此目前尚無已知的演算法能在多項式時間內解決所有圖形。

漢密爾頓迴圈與漢密爾頓路徑有何不同？

漢密爾頓迴圈是一條回到起始頂點的漢密爾頓路徑，形成一個訪問每個頂點恰好一次的封閉迴圈。每個漢密爾頓迴圈都包含一條漢密爾頓路徑（只需去掉閉合邊），但反之則不然：許多圖具有漢密爾頓路徑但沒有漢密爾頓迴圈。

Dirac 定理說了什麼？

Dirac 定理（1952 年）指出，在任何頂點數 n ≥ 3 的簡單無向圖中，如果每個頂點的度數至少為 n/2，則該圖包含一個漢密爾頓迴圈。這是一個充分但非必要條件：許多未達到 Dirac 閾值的圖仍然具有漢密爾頓迴圈。

Ore 定理說了什麼？

Ore 定理（1960 年）指出，如果對於頂點數 n ≥ 3 的簡單圖中的每一對不相鄰頂點 u 和 v，其度數之和至少為 n，則該圖具有漢密爾頓迴圈。Ore 的條件比 Dirac 的更弱，因此只要 Dirac 定理適用，Ore 定理就適用。

為什麼搜尋限制在 20 個頂點？

漢密爾頓路徑和迴圈判定問題是 NP-complete。最壞情況下的執行時間隨頂點數量呈指數級增長。透過剪枝和 Warnsdorff 啟發式，本計算機可以快速處理許多多達 20 個頂點的小型圖形，但更困難的情況可能會逾時。超過 20 個頂點，您應該使用專業的求解器，如 Concorde 或整數規劃公式。

什麼是 Warnsdorff 啟發式？

Warnsdorff 規則於 1823 年針對騎士巡邏問題提出，它指出在每一步中，您應該訪問下一個具有最少剩餘未訪問鄰居的頂點。這種看似貪婪的規則在實踐中極大地剪枝了回溯樹，並且在正則圖上通常無需回溯即可找到漢密爾頓路徑。

這款工具會找出所有漢密爾頓路徑嗎？

不會。它會在存在漢密爾頓路徑或迴圈時找到單個見證路徑。計算漢密爾頓路徑的總數本身是一個 #P-complete 問題，比判定問題難得多。對於枚舉，專門的工具或整數規劃求解器更合適。

延伸閱讀

引用此內容、頁面或工具為：

"漢密爾頓路徑檢查器" 於 https://MiniWebtool.com/zh-tw/漢密爾頓路徑檢查器/，來自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 團隊開發。更新日期：2026年4月21日

您還可以嘗試我們的 AI數學解題器 GPT，通過自然語言問答解決您的數學問題。

其他相關工具:

漢密爾頓路徑檢查器