民國112年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第72題
關於圖(Graph)的尤拉迴路(Euler Cycle),下列那些正確?
題目
關於圖(Graph)的尤拉迴路(Euler Cycle),下列那些正確?
- (1) 必須經過每一個邊正好一次
- (2) 若一個圖擁有尤拉迴路,則每個節點的度數(Degree)都是偶數
- (3) 除了起始節點以外,必須經過每一節點正好一次
- (4) 若一個圖的每個節點之度數(Degree)都是偶數,則它必定擁有尤拉迴路
官方答案
(1) 必須經過每一個邊正好一次、(2) 若一個圖擁有尤拉迴路,則每個節點的度數(Degree)都是偶數
解析
尤拉迴路(Euler Cycle/Circuit)是指在連通圖中，從某點出發、經過每一條邊「正好一次」且回到起點的封閉路徑，故選項1正確。尤拉迴路存在的充要條件是：圖為連通且每個節點的度數(Degree)皆為偶數，故選項2正確（若擁有尤拉迴路，所有節點度數必然皆為偶數）。選項3錯誤，因為「每節點正好一次」是漢米頓迴路(Hamiltonian Cycle)的特性，尤拉迴路可重複拜訪節點。選項4不嚴謹，因欠缺「連通」前提；若圖不連通（如兩個分離且皆偶數度數的子圖），即使每點皆偶數仍無單一尤拉迴路。故正確為1、2。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。