民國114年 第2梯次 延期考區 電腦軟體設計(JAVA)乙級 學科
第80題
關於圖(Graph)的尤拉迴路(Euler Cycle),下列那些正確?
題目
關於圖(Graph)的尤拉迴路(Euler Cycle),下列那些正確?
- (1) 若一個圖的每個節點之度數(Degree) 都是偶數,則它必定擁有尤拉迴路
- (2) 除了起始節點以外,必須經過每一節點正好一次
- (3) 必須經過每一個邊正好一次
- (4) 若一個圖擁有尤拉迴路,則每個節點的度數(Degree)都是偶數
官方答案
(3) 必須經過每一個邊正好一次、(4) 若一個圖擁有尤拉迴路,則每個節點的度數(Degree)都是偶數
解析
尤拉迴路的定義是經過圖中每一條邊正好一次並回到起點（選項3正確）。根據圖論定理，無向圖存在尤拉迴路的充要條件是圖連通且所有頂點度數皆為偶數，因此若擁有尤拉迴路則每個節點度數必為偶數（選項4正確）。選項1錯在缺少「連通」條件；選項2描述的是哈密頓迴路，非尤拉迴路。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。