Q252.
下列對於尤拉迴路(Euler Circuit)和漢米爾頓迴圈(Hamiltonian Cycle)的敘述那些為真？
電腦軟體設計共同科目 · 乙級 · Q252
難易度分析
3 / 5
本題要求區分兩個高度相似的圖論定義。由於選項將遍歷對象（邊與節點）進行交叉對比，且採取多選形式，考生必須對兩者定義有精確的掌握才能排除陷阱並選出所有正確答案。
正確答案 (複選)：①, ②
- ① 尤拉迴路需走過所有的邊恰一次:尤拉迴路的定義即為從某頂點出發，經過圖中每條邊恰好一次後回到起點的迴路。其存在條件為圖必須連通且所有頂點的度數均為偶數。
- ② 除起始節點外，漢米爾頓迴圈需走過所有的節點恰一次:漢米爾頓迴圈要求從某頂點出發，除起點外經過每個頂點恰好一次後回到起點。與尤拉迴路不同，它關注的是頂點的遍歷而非邊。
錯誤選項解析
- ③ 尤拉迴路需走過所有的節點恰一次:尤拉迴路的核心是遍歷所有邊而非節點，在走訪過程中頂點可被重複經過。將「邊」混淆為「節點」是此類題型的常見錯誤。
- ④ 除起始節點外，漢米爾頓迴圈需走過所有的邊恰一次:漢米爾頓迴圈的核心是遍歷所有頂點而非邊，它並不要求走過每條邊。此選項將漢米爾頓迴圈與尤拉迴路的定義顛倒混淆。
Learning Tip
"尤拉迴路與漢米爾頓迴圈的核心差異在於遍歷對象：前者走邊、後者走點。尤拉迴路有明確的充份必要條件（所有頂點度數為偶數），但漢米爾頓迴圈目前尚無簡潔的充份必要條件，屬於 NP-complete 問題。考試時務必看清題目問的是「邊」還是「節點」，避免落入文字陷阱。"
學員答題分佈
①尤拉迴路需走過所有的邊恰一次0%
②除起始節點外，漢米爾頓迴圈需走過所有的節點恰一次0%
③尤拉迴路需走過所有的節點恰一次0%
④除起始節點外，漢米爾頓迴圈需走過所有的邊恰一次0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！