Q63.
關於圖(Graph)的漢米頓迴路(Hamiltonian Cycle)，請問下列何者是錯誤的？
電腦軟體設計共同科目 · 乙級 · Q63
難易度分析
3 / 5
此題要求考生能準確區分兩種高度相似的圖論迴路定義，並對該問題的計算複雜度類別有明確認知。由於選項中設計了易混淆的對比概念，若對定義掌握不夠精準，極易落入陷阱。
正確答案：②必須經過每一個邊正好一次
② 必須經過每一個邊正好一次:此敘述錯誤。經過每條邊恰好一次的是尤拉迴路(Eulerian Circuit)，而非漢米頓迴路。漢米頓迴路關注的是頂點的遍歷，而非邊的遍歷。
錯誤選項解析
- ① 除了起點以外，必須經過每一個節點正好一次:此為漢米頓迴路的正確定義：迴路必須經過圖中每個頂點恰好一次，最後回到起點形成封閉路徑。
- ③ 判斷一個圖是否具有漢米頓迴路是NP-Complete:此為正確敘述。漢米頓迴路問題屬於NP-Complete問題，目前不存在多項式時間演算法可判定任意圖是否具備漢米頓迴路。
- ④ 若不是連結圖(Connected Graph)，則不具有漢米頓迴路:此為正確敘述。若圖為非連通圖，表示存在無法到達的頂點，因此不可能形成經過所有頂點的漢米頓迴路。連通性是漢米頓迴路的必要條件。
Learning Tip
"漢米頓迴路與尤拉迴路為圖論中最易混淆的考點：前者要求遍歷所有頂點一次，後者要求遍歷所有邊一次。實務上，判斷漢米頓迴路為NP-Complete問題，而尤拉迴路可透過檢查各頂點度數是否為偶數在多項式時間內判定，兩者計算複雜度差異為常考陷阱。"
學員答題分佈
①除了起點以外，必須經過每一個節點正好一次0%
②必須經過每一個邊正好一次0%
③判斷一個圖是否具有漢米頓迴路是NP-Complete0%
④若不是連結圖(Connected Graph)，則不具有漢米頓迴路0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！