民國112年 第2梯次 電腦軟體設計(C++)乙級 學科
第62題
關於圖(Graph)的尤拉迴路(Euler Cycle),下列那些正確?
題目
關於圖(Graph)的尤拉迴路(Euler Cycle),下列那些正確?
- (1) 若一個圖的每個節點之度數(Degree) 都是偶數,則它必定擁有尤拉迴路
- (2) 若一個圖擁有尤拉迴路,則每個節點的度數(Degree)都是偶數
- (3) 必須經過每一個邊正好一次
- (4) 除了起始節點以外,必須經過每一節點正好一次
官方答案
(2) 若一個圖擁有尤拉迴路,則每個節點的度數(Degree)都是偶數、(3) 必須經過每一個邊正好一次
解析
尤拉迴路（Euler Cycle）定義為：在連通圖中，從某點出發，每條邊恰好經過一次且回到起點的回路。故選項 3「必須經過每一個邊正好一次」正確；其必要條件是圖中每個節點的度數（Degree）皆為偶數，故選項 2「有尤拉迴路⇒每節點度數皆偶數」正確。選項 1 缺少「連通」前提，若不連通則未必存在；選項 4「每節點只經過一次」是哈密頓迴路（Hamilton Cycle）的定義，非尤拉迴路。故選 2、3。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。