民國105年 第2梯次 電腦軟體設計(C++)乙級 學科
第57題
關於圖( 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) 若不是連結圖( C o n n e c t e d G r a p h ) ,則不具有漢米頓迴路
- (3) 判斷一個 圖是否具有漢米頓迴路是N P - C o m p l e t e
- (4) 除了起點以外,必須經過每一個節點正好一次
官方答案
(1) 必須經過每一個邊正好一次
解析
漢米頓迴路定義為圖中經過每一個頂點剛好一次並回到起點的迴路。選項 1 說「必須經過每一個邊正好一次」，這其實是歐拉迴路的定義，與漢米頓迴路無關，故為錯誤敘述。選項 2 正確：非連結圖無法構成迴路。選項 3 正確：判定漢米頓迴路是經典 NP-Complete 問題。選項 4 正確描述漢米頓迴路必經每個節點一次（起點重複兩次）。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。