民國105年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第15題
關於圖( G r a p h ) 的漢米頓迴路( H a m i l t o n i a n C y c l e ),請問下列何者是錯誤的?
題目
關於圖( G r a p h ) 的漢米頓迴路( H a m i l t o n i a n C y c l e ),請問下列何者是錯誤的?
- (1) 除了起點以外,必須經過每一個節點正好一次
- (2) 判斷一個圖是否具有漢米頓迴路是N P - C o m p l e t e
- (3) 若不是連結圖( C o n n e c t e d G r a p h ),則不具有漢米頓迴路
- (4) 必須經過每一個邊正好一次
官方答案
(4) 必須經過每一個邊正好一次
解析
漢米頓迴路（Hamiltonian Cycle）要求從起點出發，經過圖中每一個「節點」恰好一次後回到起點，故選項 1 的描述正確；判斷是否存在漢米頓迴路屬於 NP-Complete 問題，選項 2 正確；圖若不連通，就不可能走訪全部節點再回到起點，選項 3 正確。選項 4 所稱「每個邊恰好一次」是尤拉迴路（Euler Circuit）的定義，並非漢米頓迴路，故為錯誤敘述。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。